# Proving equivalent definitions for MSTs

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 \}\}$$

• What is $\delta(V(C))$? I cannot find the definition of $\delta$ anywhere. – Apass.Jack Oct 15 '18 at 6:56
• It is the cut: en.wikipedia.org/wiki/Cut_(graph_theory) – 3nondatur Oct 15 '18 at 6:58
• 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)$? – Apass.Jack Oct 15 '18 at 7:04
• Yes, I will edit my question accordingly; sorry for the inconvenience. – 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.