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 (i), (ii), and (iii) are equivalent, where: (i) T has the cycle property, (ii) T has the cut property, and (iii) T is a minimum cost spanning tree.
I believe that to show that (iii) implies (i), 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 (iii) implies (ii), 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. Thank you very much.
Showing (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (i) is sufficient.
So, you can prove (i) $\Rightarrow$ (ii) by contraposition, NOT (ii) $\Rightarrow$ NOT (i). That is, suppose $T$ doesn't have the cut property. Then you can find $e' \notin T$ in a cut defined by some $e \in T$ such that $c(e') < c(e)$. But adding $e'$ to $T$ creates a cycle containing $e$, and $c(e') < c(e)$ implies $T$ doesn't have the cycle property.
Now, (ii) $\Rightarrow$ (iii). There might be more elegant ways than this, but here goes. Suppose $T$ has the cut property, and let $T'$ be a minimum spanning tree. We can transform $T$ into $T'$ by successively adding an edge $e'$ in $T'$ but not in $T$, and removing an edge in $T$ not in $T'$ that's on the cycle created by the incorporation of $e'$ (if this is homework, you might have to explain why we can do this - the idea is that every time we add an edge, a cycle is created, which must contain some edge in $T$ since the edges of $T'$ alone can't create a cycle). We can observe that for any such replacement, $e$ and $e'$ are in the same cut, and thus that $c(e) \leq c(e')$. So since every such edge of $T$ gets replaced by another edge of equal or greater weight, we have to deduce that $T$ is a minimum spanning tree as well.
And for (iii) $\Rightarrow$ (i), contrapose again. Suppose $T$ doesn't have the cycle property. Then you can find an edge $e' \notin T$ that creates a cycle with $e \in T$ such that $c(e') < c(e)$. But then, $T$ can't be a minimum spanning tree as you can replace $e$ by $e'$ in $T$ to get a smaller spanning tree.