Show that if $T,T'$ are edge-distinct minimum spanning trees of $G$, then $T$ has two edges of the same weight

354 Views Asked by At

Let $G=(V,E)$ be an undirected graph. Let $w:E\mapsto \mathbb{R}$ be a weight function over the edges. Let $T,T'$ be two minimum spanning trees with distinct edges (namely, $T\cap T' = \emptyset$). Show that there exist two different edges $e_1,e_2 \in T$ such that $w(e_1)=w(e_2)$.

I tried to prove it using Kruskal's algorithm correctness. I could not derive a contradiction...

1

There are 1 best solutions below

0
On BEST ANSWER

Let the smallest weight be $m$. If the edges of weight $m$ do not form any cycles, then they must all be included in both trees, contradicting edge-disjointness. If there is a cycle consisting of edges of weight $m$, then there must be at least three edges of weight $m$, and at least two of them must be in each of the trees, and we're done.