4
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ I don't do much graph theory, but at first glance the condition is that maximum cost edge is never in a minimal spanning tree...I thought trees didn't have circles though, so I'm not sure how that works? $\endgroup$
    – Alan
    Commented May 26, 2021 at 17:14
  • $\begingroup$ A minimal spanning tree of G is a subgraph of G. So a tree $T=(V,F) \subset G$ with the property $l(T)=min \{l(T'): T'=(V, F') \subset G: T' is a tree \}$ $\endgroup$
    – Invader
    Commented May 26, 2021 at 17:18
  • $\begingroup$ Yes, trees do not have cycles. I am not quite sure how to prove/disprove the statement. There is an algorithm (Krustal's algorithm) with which you can construct a minimal spanning tree (as explained in the question). I try to argue with that algorithm that $e$ is not part of the set of edges of the minimal spanning tree (because then we would have a cycle which cannot be) but I am not quite sure whether I can go this way $\endgroup$
    – Invader
    Commented May 26, 2021 at 17:22
  • 1
    $\begingroup$ No apologies are necessary. The flaw in your reasoning is that the other edges of the cycle may not all be in the tree by the time you get to $e'$, so the addition of $e'$ wouldn't necessarily create a cycle. I think you're on the right track though. $\endgroup$
    – saulspatz
    Commented May 26, 2021 at 17:30
  • 1
    $\begingroup$ Actually, it only takes a little refinement to complete your proof, but what it shows is that a minimal spanning tree created by Kruksal's algorithm will not contain $e'$, and we have to show that no minimal spanning tree can contain $e'$. This point escaped me at first. I'll have to think about it. $\endgroup$
    – saulspatz
    Commented May 26, 2021 at 17:49

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .