3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, but I can't figure out why $T''$ is MST. What guarantee that adding $e$ won't create a cycle in $T'$? $\endgroup$ – galah92 Feb 15 '18 at 19:54
  • $\begingroup$ @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')$. $\endgroup$ – Willard Zhan Feb 15 '18 at 21:31
  • $\begingroup$ @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? $\endgroup$ – Mickey Feb 16 '18 at 16:30
  • $\begingroup$ @Mickey No. $w(e)$ being smallest ensures $w(e')<w(e)$ cannot happen, while $T'$ being MST ensures $w(e')>w(e)$ cannot happen. $\endgroup$ – Willard Zhan Feb 16 '18 at 20:37
  • $\begingroup$ @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? $\endgroup$ – Mickey Feb 16 '18 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.