0
$\begingroup$

Let $G$ be a connected undirected graph, with integral positive weights on the edges, and let $e_1$ be an edge of $G$. As part of an assignment I proved the following Lemma 1:

The edge $e_1$ appears in any MST of $G$ iff $e_1$ is a light edge in any cut $C$ that it crosses.

Is it equivalent to the following Lemma 2?

An edge $𝑒 = (𝑢, 𝑣)$ appears in all MSTs of $𝐺$ iff every cycle including $𝑒$ has an edge $𝑒′$ with $𝑤(𝑒) < 𝑤(𝑒')$.

The latest is clearly a negation of the red rule for MSTs. I think they are equivalent but can't prove it.

$\endgroup$
  • 2
    $\begingroup$ What do you mean by equivalent? Any two true statements are equivalent. Are you asking whether there is a simple derivation of the one from the other? $\endgroup$ – Yuval Filmus Feb 15 '18 at 10:28
1
$\begingroup$

There is a serious typo/mistake in the OP's (original) question. The title say "Two criteria for an edge to belong to all MSTs". However, the lemma 1 talks about "appears in any MST". To be consistent with the title and with lemma 2, let us modify the lemma 1 as:

An edge $e$ appears in all MSTs iff $e$ is the unique lightest edge in the cut-set of some cut which $e$ crosses.

According to the title of the question, we may assume the OP's intention is to prove the two criteria for an edge to belong to all MSTs is equivalent without any reference to MST. (If reference to MST is allowed, both criteria are equivalent to the statement, the edge belongs to all MSTs. Hence both criteria are equivalent to each other as well.)

Let us state the equivalence of the two criteria clearly.

Let $G$ be a weighted connected undirected graph and $e$ an edge in $G$. The following two properties of $e$ are equivalent.

  • (unique-cut-lightest) there is a cut of $G$ such that $e$ is the unique lightest edge that crosses the cut.
  • (non-cycle-heaviest) every cycle containing $e$ contains an edge heavier than $e$.

It turns out we do have a simple proof of the above equivalence.

Unique-cut-lightest $\Rightarrow$ non-cycle-heaviest: Let $c$ be a cycle that contains $e$. As a cycle, $c$ must contains another edge in that cut-set. Name that edge $e'$. Since $e$ is the unique lightest edge in that cut-set, $e'$ is heavier than $e$.

Unique-cut-lightest $\Leftarrow$ non-cycle-heaviest: Let the vertices of $e$ be $u$ and $v$. Let us remove $e$ and all edges that is heavier than $e$ in all cycles that contains $e$ from $G$ (keeping all the vertices, however), obtaining a new graph $G'$ that share the same vertices as $G$ but with less edges. There is no path from $u$ and $v$ in $G'$; otherwise, any such path together with $e$ is a cycle in $G$ that contains no edge that is heavier than $e$, which contradicts the assumption. So $u$ and $v$ are in different connected components of $G'$. Divide the vertices of $G'$ into two sets, the vertices in the connected component of $u$ and all the other vertices. These two sets of vertices is a cut of $G$ as well. $e$ crosses that cut since $u$ is in the connected component of $u$ and $v$ is not. Since all edges other than $e$ crossing that cut is one of the removed edges, $e$ is the unique lightest edge crossing that cut.

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