Are all MST minimum spanning trees reachable by Kruskal and Prim?

I believe this is true but have not been able to get a formal proof for either. But is it true that any minimum spanning tree is reachable by applying Kruskal's algorithm? Similarly, is this true for Prim's algorithm?

EDIT: To be more precise, I want to know if given an MST for a connected, undirected, weighted graph, is it guaranteed that there is a sequence of steps using Kruskal or Prim which generates this MST. E.g. There are different choices for Kruskal when there are multiple edges with the same weight. Similarly for Prim.

As indicated by Raphael's comment and j_random_hacker's comment, the answer is positive. In fact, any MST is reachable by any MST algorithm with some minor exceptions.

For a graph $G$, two weight functions on all edges (to real numbers) are defined as (weakly) comparison-compatible (to each other) if we can extend the strict weak ordering on the edges induced by either weight function to the same strict total order. That is, we can devise consistent tie-breaking rules with each weight function so that the result of comparison of any two edges by one weight function and its tie-breaking rules is the same as the result by the other weight function and its tie-breaking rules.


Lemma 1: Let $w_1$ and $w_2$ be two weight functions. The following five statements are equivalent to each other.

• $w_1$ and $w_2$ are comparison-compatible.

• In any set of edges, there is a common lightest edge by $w_1$ and by $w_2$.

• In any set of edges, there is a common heaviest edge by $w_1$ and by $w_2$.

• There exists a weight function $w_3$ that assign distinct weights to distinct edges such that $w_3$ is comparison-compatible to $w_1$ and to $w_2$.

• for any edge $e_1$ and $e_2$ such that $e_1$ is lighter than $e_2$ by one weight function, $e_1$ is as light as or lighter than $e_2$ by the other weight function.

Proof of lemma 1 is left as an easy exercise.


Lemma 2: Let two weight functions $w_1$ and $w_2$ be such that if $e_1\lt_{w_1}e_2$, then $e_1\lt_{w_2}e_2$. Then they are comparison-comptible.

(Hint to) Proof: One approach is to verify the condition 5 of lemma 1. Another approach is to verify the condition 2 of lemma 1 by showing that in any set of edges, a lightest edge by $w_2$ is also a lightest edge by $w_1$,

A comparison-based algorithm on a graph $G$ is defined as comparison-compatible if for any two (weakly) comparison-compatible weight functions on all edges, we can run the algorithm with one weight function in a way that can be repeated without any change with the other weight function. In particular, those two runs of the algorithm will have the same output.

Please note that most if not all MST algorithms can be stated in two flavours. The first flavour assumes that distinct edges of $G$ have
distinct weights, which is used when the main concern is to find one MST (which is in fact also the unique MST). The second flavour allows distinct edges of $G$ to have same weights. Of course in this answer, where the main concern is to find all MSTs, we will only care MST algorithms in the second flavour.

A comparison-compatible MST algorithm can find all MSTs.

To prove the above proposition, we just need to adapt slightly the section, "Kruskal can find every MST" in the computation of the number of MSTs. For any MST $m$ of $G$ with weight function $w_1$, choose a positive weight that is lighter than the absolute difference between any pair of unequal edge weights. If we subtract that weight from the weight of each edge in $m$ without changing weights of other edges, we obtain a new weight function, say, $w_2$. If edge $e_1$ is lighter than $e_2$ by $w_1$, $e_1$ must be lighter than $e_2$ by $w_2$ as well. By lemma 2, $w_1$ and $w_2$ are comparison-compatible. Note that $m$ is the unique MST with $w_2$. (One way to show this uniqueness is to prove that whenever the weight of one MST edge is reduced, any MST with the new weight function must contain that edge.) So any run of the algorithm on $w_2$ will find $m$. Because the algorithm is comparison-compatible, we can run the algorithm the same way with $w_1$ or with $w_2$. Since that run will find the unique MST, $m$ with $w_2$, it will find $m$ as well with $w_1$.

Every MST algorithm is comparison-compatible

The above proposition sounds overbroad. Well, by every MST algorithm, I mean any general comparison-based MST algorithm that I have seen, excluding those apparently pathological ones such as wrong or having unnecessary steps. Since a comparison-compatible MST algorithm can find all MSTs, every MST algorithm can find all MSTs. In particular, each of the four classic MST algorithms, namely Borůvka's, Prim's, Kruskal's and reverse-delete algorithms can find all MSTs.

Here are three more comparison-compatible MST algorithms.

• the delete-heavy-edge algorithm. Start with all edges. Repeatedly find a cycle and remove one of its heaviest edge until no cycle remains.

• the add-non-heavy-edge algorithm. Start with the empty set. Iterate through all edges. Each edge is added and, if a cycle is formed, remove one of it heaviest edges.

• the replace-by-lighter-edge algorithm. Start with any spanning tree $T$.

Find the cycle in $T$ plus an edge $e$ not in $T$. If an edge $t$ in that cycle is heavier than $e$, remove $t$ from $T$ and add $e$ to $T$. Repeat until we cannot reduce the weight of $T$ any more.

The following MST algorithm is not comparison-compatible.

• the degree-biased Kruskal's algorithm, which is Kruskal's algorithm

StackExchange Computer Science Q#91539, answer score: 12