De-contracting minimum spanning trees

Question

I'm thinking about how to prove the following statement on Wikipedia. Assume an undirected graph with weights for each edge.

If $T$ is a tree of MST edges, then we can contract $T$ into a single vertex while maintaining the invariant that the MST of the contracted graph plus $T$ gives the MST for the graph before contraction.

The linked paper just states that this is a well known fact.

---

What I have so far: We can reduce the question to contracting a single edge and iteratively apply that to the subgraph of the MST.

Let $G$ be an undirected graph with weights $c \colon E(G) \to \mathbb R$. Assume $T$ is an MST in $G$ and let $e \in E(T)$. Let $G/e$ be the Graph after contracting $e$ and let $T'$ be a MST in $G/e$. We claim that $T'+e$ is a MST in $G$.

Since $E(G/e) = E(G) \setminus \{e\}$, the cycle property is satisfied for $T'+e$ except for all Edges $f \notin E(T'+e)$ s.t. the cycle in $(T'+e)+f$ contains $e$. But then...

---

Another thought: If all edge weights are unique, i.e. $c$ is injective, than the proof is immediate. In this case, MSTs are unique. $T/e$ is the only MST in $G/e$. But can we assume wlog that $c$ is injective?

Answer 1

Let $uv$ be an arbitrary edge. There is a cost-preserving bijection between $E(G) - \{uv\}$ and $E(G/uv)$. Under this bijection:

• If $T$ is a spanning tree of $G/uv$, then the corresponding edges in $G$ still allow every vertex to reach either $u$ or $v$. Since there are not enough of them to be a spanning tree, these edges must form a spanning forest with one component containing $u$ and one component containing $v$. Adding edge $uv$ forms a spanning tree.
• Conversely, if $T$ is a spanning tree of $G$ containing $uv$, then $T-uv$ is a two-component spanning forest with one component containing $u$ and one component containing $v$. Therefore the corresponding edges in $G/uv$ are spanning, which (by counting the edges) makes them a spanning tree.

Therefore we also have a nearly-cost-preserving bijection between spanning trees of $G/uv$ and spanning trees of $G$ containing $uv$: the bijection changes the total cost by a fixed value, which is the cost of edge $uv$. In particular, the MSTs of $G/uv$ correspond to the spanning trees of $G$ containing $uv$ which have the lowest cost out of all such trees.

If, in fact, $uv$ is part of at least one MST of $G$, then we conclude that the MSTs of $G/uv$ correspond to the MSTs of $G$ containing $uv$ under the bijection.