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
- T has the cycle property,
- T has the cut property, and
- 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.