1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.