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

2 Answers 2

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$
9
  • $\begingroup$ Why in the proof of the lemma T' is MST? We haven't assumed that. $\endgroup$
    – sooobus
    May 16, 2016 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, 2016 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, 2016 at 9:10
  • $\begingroup$ @sooobus That is because $w(e) = w(e')$. $\endgroup$
    – hengxin
    May 16, 2016 at 9:21
  • 1
    $\begingroup$ @sooobus If any edge $e''$ has the maximal weight on the cycle created by adding $e''$ to some spanning tree $T'$ (the original one), then it also has the maximal weight on the cycle (if exists) created by adding $e''$ to the spanning tree $T''$ ($T'' = T' + e - e'$) because $T'$ and $T''$ differ only by $e$ and $e'$ and that $w(e) = w(e')$. $\endgroup$
    – hengxin
    May 16, 2016 at 9:29
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$
3
  • $\begingroup$ Why is that "$uv$ has a larger weight than $ab$"? I do not get it. $\endgroup$
    – hengxin
    May 15, 2016 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, 2016 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, 2016 at 14:16

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.