I am working on the following homework exercise:

Let $G = (V,E)$ be an undirected graph and $c: E \rightarrow \mathbb{R}$ it's cost function. Further let $T = (V,E')$ be a spanning tree in G.

I need to show the equivalence of the following statements:

  1. $T$ is a MST.
  2. For all $e = \{x,y\} \in E \setminus E'$ holds: No edge of the (unique) path from $x$ to $y$ has a higher cost than $e$.
  3. For all $e \in E'$ holds: Let $C$ one of the two connected components of $T-e$, then $e$ is an edge with minimal weight in $\delta(V(C))$.

I have done $1) \implies 2)$ and $2) \implies 3)$, but I do not know how to prove $3) \implies 1)$. Could you give me a hint?

EDIT: Please note that $\delta$ refers to the cut, i.e.:

$$\delta(X) = \{ \ \{u,v\} \in E(G) : u \in X \text{ and } v \notin X \}\}$$

  • $\begingroup$ What is $\delta(V(C))$? I cannot find the definition of $\delta$ anywhere. $\endgroup$ – John L. Oct 15 '18 at 6:56
  • $\begingroup$ It is the cut: en.wikipedia.org/wiki/Cut_(graph_theory) $\endgroup$ – 3nondatur Oct 15 '18 at 6:58
  • $\begingroup$ That is what I suspected. However, as in the Wikipedia entry, a cut or a cut-set is usually specified by both vertex subsets of a partition of $V$. Do you mean the cut-set $(V(C), V\setminus V(C)$? $\endgroup$ – John L. Oct 15 '18 at 7:04
  • $\begingroup$ Yes, I will edit my question accordingly; sorry for the inconvenience. $\endgroup$ – 3nondatur Oct 15 '18 at 7:11

In order to make sure $3)\implies1)\,$ is true, let us assume that all costs of edges are different. Otherwise, there is a counterexample at Is a set of acyclic |V| - 1 light edges always a Minimum Spanning Tree?.

Here is a hint to prove $3) \implies 1)\,$. Suppose you have some MST $T'$. Show that $T$ and $T'$ have the same number of edges. Show that $T'$ must contain every minimal cut.


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.