Spanning Tree - Equivalent Properties

Question

I am working on the following problem:

Suppose that $T$ is a spanning tree of a graph $G$, with an edge cost function $c$. Let $T$ have the cycle property if for any edge $e' \not \in T, c(e') \geq c(e)$ for all $e$ in the cycle generated by adding $e'$ to $T$. Let $T$ have the cut property if for any edge $e \in T$, $c(e) \leq c(e')$ for all $e'$ in the cut defined by $e$.

Show that the following three properties are equivalent

1. T has the cycle property,
2. T has the cut property, and
3. T is a minimum cost spanning tree.

I believe that to show that 3. implies 1., we suppose otherwise, and then show that this would give a cycle with an edge that can replace another edge in T and that is cheaper, whence we have a contradiction. Similarly, I believe to show that 3. implies 2., we similarly suppose otherwise, and then show that this would give a cut with an edge that can replace another edge in T and that is cheaper, whence a contradiction.

However, I am not sure how to prove the other implications needed for this problem. My feeling is to somehow use a similar argument to what I listed, but "in reverse".

Any help with this problem would be greatly appreciated.

Answer 1

Continuing where @ijkilchenko left off.

$2\to 3$: Let $T$ have the cut property and let $T'$ be any other spanning tree of $G$. For each $e\in T$, there is some edge $e'\in T'$ that crosses the cut defined by $e$. Define $f : E(T) \to E(T')$ by mapping each edge $e \in E(T)$ to the edge $e' \in E(T)'$ with smallest weight among those crossing the cut defined by $e$. According to the cut property $w(e)\le w(f(e))$, so we get $$ w(T) = \sum_{e \in T} w(e) \le \sum_{e\in T} w(f(e))\le \sum_{e'\in T'} w(e') = w(T')$$ where the third inequality comes from the fact that if $f$ is not injective, it only decreases weights. Since $T'$ was arbitrary, we have shown that $w(T)$ is minimum among all spanning trees of $G$, and we are done.

$3\to 1$: If $T$ does not have the cycle property, the definition supplies us with an edge $e\in T$ and $e'\notin T$ such that $w(e') < w(e)$, so $T - e + e'$ is a tree with weight less than $T$. Therefore $T$ does not have minimum weight.

Answer 2

1 $\Rightarrow$ 2: Suppose that $T$ has the cycle property. Fix $e\in T$. The edge $e$ will define our cut because removing $e$ from $T$ will give us two disconnected components $T_1$ and $T_2$. Adding any edge $e'$ between $T_1$ and $T_2$ gives us a cycle in $T + e'$ that necessarily goes through $e$. By the cycle property, $c(e) \leq c(e')$.

To finish the problem, show that $2\Rightarrow 3$ and $3\Rightarrow 1$. Hope this helps.