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: A different route to the same conclusion uses a direct exchange argument on Kruskal's algorithm rather than naming the two properties up front.

Step 2: Option (A). Suppose, for contradiction, that the largest weight edge \(e\) of some cycle \(C\) were present in an MST \(T\). Removing \(e\) from \(T\) splits \(T\) into two components. Since \(e\) lies on cycle \(C\), the rest of \(C\) (all of it strictly lighter than \(e\) because weights are unique and \(e\) is the maximum) supplies another edge \(f\) that reconnects the same two components. Swapping \(f\) in for \(e\) gives a spanning tree of strictly smaller total weight, contradicting that \(T\) was minimum. So \(e\) can never be in an MST, confirming (A).

Step 3: Option (D). Fix vertex \(v\) and let \(e^{*}\) be its cheapest incident edge. If some MST \(T\) excluded \(e^{*}=(v,w)\), then in \(T\), \(v\) is reached by some other, strictly costlier edge \(e'\) (unique weights rule out a tie). Removing \(e'\) from \(T\) isolates \(v\) from the rest; adding \(e^{*}\) back reconnects \(v\) at strictly lower cost, again shrinking the total weight, a contradiction. So \(e^{*}\) must be in every MST, confirming (D).

Step 4: Options (B) and (C) fail because a single edge can be extremal in more than one local structure with opposite implications. Build the graph \(a\text{-}d=0.1,\ d\text{-}c=0.05,\ a\text{-}c=1,\ a\text{-}b=2,\ b\text{-}c=3\). Edge \(a\text{-}c\) is the lightest edge of triangle \(a,b,c\) (weights \(1,2,3\)) yet the heaviest edge of triangle \(a,d,c\) (weights \(0.1,0.05,1\)). By the exchange argument of Step 2, the second fact forces \(a\text{-}c\) out of the MST, so being the lightest edge of one cycle does not guarantee MST membership: (B) is false. For (C), a degree-1 vertex has its unique incident edge acting as both the heaviest and lightest edge at that vertex, and Step 3's argument forces that edge into every MST, so the heaviest edge at a vertex is not always excluded: (C) is false.

Step 5: This exchange-argument route reaches the identical conclusion as the named-property route.

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