Question

Let \(G(V,E)\) be a simple, undirected graph with unique edge weights.
Which of the following statements about the minimum spanning trees (MST) of \(G\) is/are true?

• A. In every cycle \(C\) of \(G\), the edge with the largest weight in \(C\) is not in any MST
• B. In every cycle \(C\) of \(G\), the edge with the smallest weight in \(C\) is in every MST
• C. For every vertex \(v \in V\), the edge with the largest weight incident on \(v\) is not in any MST
• D. For every vertex \(v \in V\), the edge with the smallest weight incident on \(v\) is in every MST

Hint:

Use the Cycle Property (max edge of a cycle is never in an MST) and the Cut Property applied to the single-vertex cut (min edge at a vertex is always in the MST).

Answer 1

The Correct Option is A, D

Step 1: Concept.
Two standard structural facts govern every MST of a weighted graph.
Cycle Property: if an edge \(e\) is the strict maximum weight edge in some cycle \(C\) of \(G\), then \(e\) belongs to no MST of \(G\).
Cut Property: if an edge \(e\) is the strict minimum weight edge crossing some cut \((S, V-S)\) of \(G\), then \(e\) belongs to every MST of \(G\).
Since all edge weights of \(G\) are pairwise distinct, any maximum or minimum taken over a cycle or a cut is automatically strict, so both properties apply without any tie-breaking concerns.

Step 2: Check option (A).
In any cycle \(C\), the edge of largest weight is, by uniqueness of weights, the strict maximum weight edge of \(C\). The Cycle Property says this edge cannot lie in any MST. So (A) is TRUE for every cycle of \(G\).

Step 3: Check option (B) with a counterexample.
Take vertices \(a,b,c,d\) with edges \(d\text{-}c=0.05,\ a\text{-}d=0.1,\ a\text{-}c=1,\ a\text{-}b=2,\ b\text{-}c=3\).
Cycle \(a\text{-}b\text{-}c\text{-}a\) has weights \(2,3,1\); its smallest weight edge is \(a\text{-}c=1\).
Running Kruskal's algorithm on the whole graph in increasing weight order: add \(d\text{-}c(0.05)\), add \(a\text{-}d(0.1)\), reject \(a\text{-}c(1)\) since \(a,d,c\) are already connected, add \(a\text{-}b(2)\) which completes a spanning tree on 4 vertices with 3 edges, reject \(b\text{-}c(3)\).
The unique MST is \(\{d\text{-}c,\ a\text{-}d,\ a\text{-}b\}\), which does NOT contain \(a\text{-}c\) even though \(a\text{-}c\) was the smallest weight edge of cycle \(a\text{-}b\text{-}c\text{-}a\).
The reason is that \(a\text{-}c\) is simultaneously the strict maximum weight edge of the different cycle \(a\text{-}d\text{-}c\text{-}a\) (weights \(0.1, 0.05, 1\)), so the Cycle Property excludes it there. Hence (B) is FALSE in general.

Step 4: Check option (C) with a counterexample.
Take any vertex \(v\) of degree 1 in \(G\), i.e. \(v\) has exactly one incident edge \(e\). That single edge is simultaneously the largest weight and the smallest weight edge incident on \(v\). Since \(e\) is the only link to \(v\), it is a bridge and must be present in every spanning tree of \(G\), including every MST. So the claim that the largest weight edge incident on \(v\) is never in any MST fails whenever some vertex has degree 1. Hence (C) is FALSE in general.

Step 5: Check option (D).
Fix any vertex \(v\) and consider the cut \((\{v\}, V-\{v\})\). The edges crossing this cut are exactly the edges incident on \(v\). Because all weights are distinct, there is a unique minimum weight edge among them, say \(e^{*}\). By the Cut Property, \(e^{*}\) belongs to every MST of \(G\); \(e^{*}\) is precisely the smallest weight edge incident on \(v\). So (D) is TRUE for every vertex.
Verifying on the Step 3 example: minimum edge at \(a\) is \(a\text{-}d(0.1)\) (in MST), at \(b\) is \(a\text{-}b(2)\) (in MST), at \(c\) is \(d\text{-}c(0.05)\) (in MST), at \(d\) is \(d\text{-}c(0.05)\) (in MST) - consistent every time.

Step 6: Conclusion.
(A) and (D) are always true (Cycle Property and Cut Property on vertex-cuts respectively). (B) and (C) fail, as shown by explicit counterexamples.

\[ \boxed{\text{Correct options: (A) and (D)}} \]