# How can Kruskal's algorithm return different spanning trees?

We assume that we have the same graph G.

In introduction to Algorithms by Cormen it's said that its possible depending on how it breaks ties when the edges are sorted into order.

I have trouble visualizing the answer given:

Suppose that A is an empty set of edges. Then, make any cut that has (u, v) crossing it. Then, since that edge is of minimal weight, we have that (u, v) is a light edge of that cut, and so it is safe to add. Since we add it, then, once we finish constructing the tree, we have that (u, v) is contained in a minimum spanning tree.

What does it mean to make a cut? I$$$$m familiar with Kruskal's algorithm but nowhere in the process do I see cuts being made. It's either we unite two trees and add the edge to A or we reject the edge and continue on.

• That depends on the ordering of the elements. If you choose a different order, than you may select a different edge from the same lengths. – kelalaka Feb 24 '20 at 18:01

• Yes, it only requires that if weight of edge $e_i$ is lower than weight of $e_j$, it's considered earlier, but edges with equal weights can be considered in any order. – Alexey Romanov Feb 24 '20 at 17:37