It seems like, given an undirected graph $G = (V, E)$ with distinct edge weights, one only needs an ordering on $E$ to run Kruskal's algorithm. This tells me that the (distinct) minimum spanning tree of $G$ only depends on $E$'s ordering, and not the actual edge weights themselves. So given that one only knows an ordering on $E$ we can still compute the minimum spanning tree of $G$.

The intuition of what a minimum spanning tree is pretty clear to me: it's just a spanning tree that minimizes the weight of the tree. But we can still run Kruskal's algorithm without ever having any edge weights, only an ordering on $E$, and still getting a spanning tree back. Is there any intuitive sense in which this tree can be considered "minimal", without endowing $E$ with weights compatible with the ordering on $E$, and then calling it minimal with respect to these artificially constructed edge weights?

I wrote a short program that generates small random graphs, fixes an edge order on each random graph, adds edge weights consist with the edge order (randomly, a few different ways), and then run an MST algorithm to check that I get the same spanning tree each time.

  • 1
    $\begingroup$ The proof of correctness of Kruskal's algorithm should give some insight. $\endgroup$
    – Laakeri
    Jan 5 at 23:36
  • $\begingroup$ This is what I was inclined to read as well. Following the proof of correctness given on Wikipedia (en.wikipedia.org/wiki/Kruskal%27s_algorithm#Minimality), the proposition $P$ that is true of any intermediate subgraph $F$ in the inductive construction still references the "minimum" spanning tree definition, in that $F$ is required to be contained in some minimum spanning tree. So as far as I can tell, one would still have to adequately generalize what a "minimum" spanning tree is, and that's what I'm struggling with at the moment. $\endgroup$ Jan 5 at 23:53
  • 2
    $\begingroup$ You don't need weights for a well-defined notion of minimum. E.g. (an appropriately defined) lexicographically minimum would do, surely. $\endgroup$
    – Neal Young
    Jan 7 at 20:40
  • $\begingroup$ Understood that we could use a different total order on spanning trees, other than what's induced by edge weights. What would be the components of the tuples in the lex order on spanning trees that you're proposing? $\endgroup$ Jan 8 at 22:48


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.