# Between every two MST's there's a series of “nearby” MST's

Given undirected connected graph $G=(V,E)$ and a weight function $w:E\to\mathbb{R}$, two MST's $T_1, T_2$ are nearby if there exists $e\in T, e'\in T'$ such that $T'=(T-\{e\})\cup\{e'\}$.

Prove that for every $T, T'$ there exists a series of $T=T_1,T_2,...,T_k=T'$ such that every two consecutive MST's are nearby each other.

I started proving it using induction but it didn't work. Assume I have $T,T'$ that has $k+1$ distinct edges each, and I know (by induction assumption) that each two MST's with $k$ distinct edges has a series between them, what can I do next? All I know is that the sum of those $k+1$ edges in each MST is equal.

Thanks.

Here is how you make progress from $k+1$ distinct edges to $k$ distinct edges.

Suppose $T$ and $T'$ has $k+1$ distinct edges, which refer to $k+1$ edges in $T$ and another $k+1$ edges in $T'$ and they are all distinct. Among these $2k+2$ edges suppose $e\in T$ has the smallest weight.

Adding $e$ to $T'$ results in a cycle $C\subseteq T'\cup\{e\}$. If there is an edge $e'\in C$ such that $w(e')=w(e)$ and $e'\notin T$, then we are done: let $T''=(T'\cup\{e\})-\{e'\}$, and now $T''$ has $k$ distinct edges with $T$, while $T''$ and $T'$ are nearby.

The rest is to show that such an edge $e'$ always exists. Since $C$ cannot be entirely contained in $T$, there must be an edge $e'\in C$ that $e'\notin T$. I leave it to you to verify that either $w(e')<w(e)$ or $w(e')>w(e)$ cannot happen, so it must holds $w(e')=w(e)$ and that $e'$ is what we want.

• Thank you, but I can't figure out why $T''$ is MST. What guarantee that adding $e$ won't create a cycle in $T'$? – galah92 Feb 15 '18 at 19:54
• @galah92 Adding $e$ to $T'$ must create a (fundamental) cycle $C$, and deleting an edge $e'$ from $C$ makes it back to a spanning tree. Why $T''$ is an MST is because $w(T'')=w(T')$. – Willard Zhan Feb 15 '18 at 21:31
• @WillardZhan Why do you take the edge with the smallest weight from the $2k+2$ edges? Shouldn't it be the edge with the highest weight? – Mickey Feb 16 '18 at 16:30
• @Mickey No. $w(e)$ being smallest ensures $w(e')<w(e)$ cannot happen, while $T'$ being MST ensures $w(e')>w(e)$ cannot happen. – Willard Zhan Feb 16 '18 at 20:37
• @WillardZhan I'm still not sure why your constraint on the weight of the chosen edge is necessary. As far as I see, there will always be an edge $e'$ that satisfies $w(e')=w(e)$ in the circle. Assume there doesn't exist such edge. Than either $w(e')>w(e)$ or $w(e')<w(e)$. W.L.G assume the first. Then by replacing $e'$ with $e$ in $T'$ we get $w(T'_{\text{new}})<w(T')$ and therefore $T'$ wasn't an MST, in a contradiction. Can you please elaborate on that? – Mickey Feb 16 '18 at 21:08