<p>It seems like, given an undirected graph <span class="math-container">$G = (V, E)$</span> with distinct edge weights, one only needs an ordering on <span class="math-container">$E$</span> to run Kruskal's algorithm. This tells me that the (distinct) minimum spanning tree of <span class="math-container">$G$</span> only depends on <span class="math-container">$E$</span>'s ordering, and not the actual edge weights themselves. So given that one only knows an ordering on <span class="math-container">$E$</span> we can still compute the minimum spanning tree of <span class="math-container">$G$</span>.</p>
<p>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 <span class="math-container">$E$</span>, and still getting a spanning tree back. Is there any intuitive sense in which this tree can be considered &quot;minimal&quot;, without endowing <span class="math-container">$E$</span> with weights compatible with the ordering on <span class="math-container">$E$</span>, and then calling it minimal with respect to these artificially constructed edge weights?</p>
<p>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.</p>

CC BY-SA 4.0
2024-01-05T23:36:54.003Z
The proof of correctness of Kruskal's algorithm should give some insight.
Laakeri
CC BY-SA 4.0
2024-01-05T23:53:44.933Z
This is what I was inclined to read as well. Following the proof of correctness given on Wikipedia (https://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.
Vikram Saraph
CC BY-SA 4.0
2024-01-07T20:40:11.373Z
You don't need weights for a well-defined notion of minimum.  E.g. (an appropriately defined) lexicographically minimum would do, surely.
Neal Young
CC BY-SA 4.0
2024-01-08T22:48:26.763Z
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?
Vikram Saraph
<graph-algorithms><spanning-tree>
Minimum spanning tree with only edge ordering
Vikram Saraph
# Minimum spanning tree with only edge ordering

(Asked by: username_0 on 2024-01-05)

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.

**Tags:** graph-algorithms, spanning-tree
> **Comments:**
> **username_1**: The proof of correctness of Kruskal's algorithm should give some insight.  
> **username_0**: This is what I was inclined to read as well. Following the proof of correctness given on Wikipedia (https://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.  
> **username_2**: You don't need weights for a well-defined notion of minimum.  E.g. (an appropriately defined) lexicographically minimum would do, surely.  
> **username_0**: 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?  

---

## 0 answers

