4
$\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$
2

1 Answer 1

2
$\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$
8
  • $\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, 2018 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$
    – Wei Zhan
    Feb 15, 2018 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, 2018 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$
    – Wei Zhan
    Feb 16, 2018 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, 2018 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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