1
$\begingroup$

Prove that $T$ is MST $\Leftrightarrow$ for any edge $uv \notin T$, $uv$ has the maximal weight on the cycle created by adding $uv$ to $T$.

It's my attempt to prove $\Rightarrow$: Consider the cycle $path(v, u) \in T \cup E(v, u)$. If $(v, u)$ is not maximal, replace the maximal edge on the path by $(v, u)$. T is still connected, and we got spanning tree which weight is less than $w(T)$.

But I am stuck with the direction of "$\Leftarrow$".

$\endgroup$
  • $\begingroup$ My original answer has a flaw in the claim of "without loss of generality". Please check the updated one. $\endgroup$ – hengxin May 16 '16 at 1:08
1
$\begingroup$

Note: The original answer has a flaw in "without loss of generality". The following one is based on Section 8.2.3 of the book "Computer Algorithms" (3rd edition) by Sara Baase and Allen Van Gelder.


The right part of the theorem is called the MST property.

MST Property: Let $T$ be any spanning tree. For any edge $e \notin T$, $e$ has the maximal weight on the cycle created by adding it to $T$.

In terms of the MST property, the theorem to prove can be restated as:

A spanning tree $T$ is an MST $\iff$ $T$ has the MST property.


We first prove the following lemma:

Lemma: If $T$ and $T'$ are spanning trees that have the MST property, then $w(T) = w(T')$.

Proof: Let $\Delta E = (E(T) \setminus E(T')) \cup (E(T') \setminus E(T))$. That is, $\Delta E$ is the set of edges that are in one of $T$ or $T'$ but not in both. $\Delta E \neq \emptyset$. Let $|\Delta E| = k$.

If $k = 0$, we are done.

Let $k > 0$ and $e$ be a minimum edge in $\Delta E$. Assume that $e \in T \setminus T'$ (the case of $e \in T' \setminus T$ is symmetrical).

$T' + e$ create a cycle $C_{T'}$. There must be an edge $e'$ on the cycle $C_{T}$ that $e' \neq e$ and $e' \in T' \setminus T$ (otherwise $T$ contains the cycle $C_{T'}$).

  • Since $T'$ has the MST property, $e$ has the maximum weight on the cycle $C_{T'}$. Thus, $w(e') \le w(e)$.
  • On the other hand, $e$ by definition is a minimum edge in $\Delta E$. Thus, $w(e) \le w(e')$.

Therefore, $w(e) = w(e')$.

Add $e$ to $T'$, creating a cycle, then remove $e'$, leaving a spanning tree $T''$. Since $w(T'') = w(T')$, $T''$ is an MST. However, $T$ and $T''$ differ by $k-1$ edges.

Repeating the procedure above, we will end with an MST, say $T^{k+1}$, such that $T$ and $T^{k+1}$ differ by $0$ edges.

Therefore, we have $w(T) = w(T^{k+1}) = \cdots = w(T'') = w(T')$.


Given the lemma above, we proceed to prove the "$\Leftarrow$" direction as follows:

Assume $T$ has the MST property. Let $T_m$ be any MST. By the "$\Rightarrow$" direction, $T_m$ has the MST property. By the lemma above, $w(T) = w(T_m)$. Thus, $T$ is an MST.

$\endgroup$
  • $\begingroup$ Why in the proof of the lemma T' is MST? We haven't assumed that. $\endgroup$ – sooobus May 16 '16 at 8:33
  • $\begingroup$ @sooobus Sorry. It was a mistake I have not corrected when I updated the answer. It only relies on the fact that "$T'$ has the MST property". $\endgroup$ – hengxin May 16 '16 at 8:43
  • $\begingroup$ Could you please explain, why when we substitute e' by e the MST property doesn't break $\endgroup$ – sooobus May 16 '16 at 9:10
  • $\begingroup$ @sooobus That is because $w(e) = w(e')$. $\endgroup$ – hengxin May 16 '16 at 9:21
  • $\begingroup$ But the new edge can form another set of cycles, and it they can not have the property $\endgroup$ – sooobus May 16 '16 at 9:22
0
$\begingroup$

Assume that there is a minimum spanning tree $T'$ with smaller weight than $T$. Since $T\neq T'$ there has to be an edge $uv$ in $T'$ but not in $T$. Now remove $uv$ from $T'$. This splits $T'$ into two trees $T'_u$ and $T'_v$. We denote the vertices spanned by $T'_u$ by $U$ and the vertices spanned by $T'_V$ by $V$. Let $\pi$ be the path that connects $u$ with $v$ in $T$. When traveling along $\pi$ we will leave at some point the set $U$ and enter the vertex set $V$. Assume that this "jump" happens at edge $ab$. Since $uv$ has a larger weight than $ab$ we get that $T'\setminus \{uv\} \cup \{ab\}$ has a smaller weight than $T'$ (and is of course a spanning tree). Hence $T'$ cannot be a MST and we have a contradiction to our assumption that there is a spanning tree with smaller weight than $T$.

$\endgroup$
  • $\begingroup$ Why is that "$uv$ has a larger weight than $ab$"? I do not get it. $\endgroup$ – hengxin May 15 '16 at 13:39
  • $\begingroup$ @hengxin Well, $\pi$ with $uv$ forms a cycle, with all the edges of this cycle from $T$ except $uv$. Then by the assumption the weight of $uv$ is larger than any weight of the other edges in this cycle. Since $ab$ is in this cycle we get that the weight of $uv$ is larger than the weight of $ab$. $\endgroup$ – A.Schulz May 15 '16 at 14:11
  • 1
    $\begingroup$ However, the edges with the maximal weight (on the cycle) may not be unique. I think we can only conclude that $w(uv) \ge w(ab)$. $\endgroup$ – hengxin May 15 '16 at 14:16

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.