Prove or disprove: The edge $e$ is not included in any minimal spanning tree of G

graph theory

Let $G=(V,E,l)$ be a connected, undirected, weigthed Graph. Let $C=(V',E')$ be a cycle in $G$ and $e \in E'$ with $l(e) > l(e')$ $ \forall e' \in E'$\ $\{e\} $. Prove or disprove: The edge $e$ is not included in any minimal spanning tree of $G$. $l$ is the weight function assigning weights to every edge.

I know Kruskal's algorithm to construct a minimal spanning tree, but I have no clue how to prove or disprove the statement. How would one approach this problem? In Krustal's algorithm we sort the edges by their weight. Then we loop through the sorted edges and put it in the set of edges of the minimal spanning tree if the edges do not form a cycle. That means before we even consider to put the edge $e$ in the set of edges, all other edges of the cycle would be contained in the set. That would mean we would not be able to put the edge $e$ in the set because then the minimal spanning tree would contain a cycle which is not allowed. So the statement must be true? How would a rigorous prove/disprove would look like here?

Best Answer

Arguing by contradiction, suppose that $T$ is a minimal spanning tree that contains $e$.

When $e$ is removed from $T$, the result is a disjoint pair of subtrees $T_1$, $T_2$: $$T - e = T_2 \cup T_2 $$ When $e$ is removed from the cycle $C$, the result is an arc $A$. This arc $A$ has one endpoint on $T_1$ denoted $v_1$ and its opposite endpoint on $T_2$ denoted $v_2$.

So now I need to carefully analyze the structure of the arc $A$. As you travel along $A$ from $v_1$ to $v_2$, list the edges of $G - (T_1 \cup T_2)$ that occur in order $e_1,...,e_K$. Note that $K \ge 1$, because $A$ starts at $v_1 \in T_1$ and ends at $v_2 \in T_2$ and so $A$ must cross at least one edge of $G - (T_1 \cup T_2)$ along the way. We can then write $A$ is a concatenation of the form $$A = \alpha_0 \, e_1 \, \alpha_1 \, e_2 \, \alpha_2 \, \cdots \, e_K \, \alpha_K $$ where:

  • $\alpha_0$ is the portion of $A$ preceding $e_1$ (either a subarc with one endpoint at $v_1$ and opposite endpoint on $e_1$, or is just the single point $v_1$).
  • for $1 \le i \le K-1$, $\alpha_i$ is the portion of $A$ between $e_i$ and $e_{i+1}$ (which is either a subarc with one endpoint on $e_i$ and opposite endpoint on $e_{i+1}$, or is just a single point where $e_i$ meets $e_{i+1}$)
  • $\alpha_K$ is the portion of $A$ following $e_K$ (either a subarc with one endpoint on $e_K$ and opposite endpoint on $v_2$, or just a single point $v_K$).

Here are the key additional facts needed:

  • $\alpha_0$ is contained in $T_1$
  • For $1 \le i \le K-1$, $\alpha_i$ is contained in either $T_1$ or in $T_2$;
  • $\alpha_K$ is contained in $T_2$.

It follows that as $i$ increases from $1$ to $K$, there exists $i$ such that $\alpha_{i-1}$ is in $T_1$ and $\alpha_i$ is in $T_2$. Therefore $e_i$ has one endpoint on $T_1$ and opposite endpoint on $T_2$.

Now define $$T' = T_1 \cup T_2 \cup e_i $$ This is a spanning tree of $G$. But because $l(e) > l(e_i)$, it follows that $T'$ has smaller total weight than $T$. This contradicts that $T$ is a minimal spanning tree.

Related Question