Question

Let 𝐺(𝑉, 𝐸) be a simple, undirected, edge-weighted graph with unique edge weights.
Which of the following statements about the minimum spanning trees (MST)
of 𝐺 is/are true?

• A. In every cycle 𝐶 of 𝐺, the edge with the largest weight in 𝐶 is not in any MST
• B. In every cycle 𝐶 of 𝐺, the edge with the smallest weight in 𝐶 is in every MST
• C. For every vertex 𝑣 ∈𝑉, the edge with the largest weight incident on 𝑣 is not in any MST
• D. For every vertex 𝑣 ∈𝑉, the edge with the smallest weight incident on 𝑣 is in every MST

Hint:

Use two classical facts for a graph with unique edge weights: the Cycle Property (the maximum weight edge in any cycle is never in the MST) and the Cut Property (the minimum weight edge crossing any cut, including the trivial cut isolating one vertex, is always in the MST). Test the reversed claims with a small counterexample graph and a degree-1 vertex.

Answer 1

The Correct Option is A, D

Step 1: Setup. Since all edge weights of \(G\) are distinct, \(G\) has a unique Minimum Spanning Tree (MST). Two standard results decide every option here: the Cycle Property and the Cut Property.

Step 2: Check Option A (Cycle Property). The Cycle Property states that for any cycle \(C\) in \(G\), the edge with the maximum weight in \(C\) can never belong to any MST. Reason: if this maximum edge were in a spanning tree, removing it and adding any other edge of \(C\) instead would reconnect the tree with strictly lower total weight, so the max-weight edge is always a bad choice. Hence Option A is true.

Step 3: Check Option B (counterexample). Take vertices \(A, X, B, C\) with edges \(AX=1, XB=2, AB=3, BC=4, CA=5\). Consider the cycle \(A\text{-}B\text{-}C\text{-}A\) formed by edges \(AB=3, BC=4, CA=5\); the smallest weight edge in this cycle is \(AB=3\). Running Kruskal on the whole graph: add \(AX(1)\), add \(XB(2)\) (now \(A, X, B\) are connected), then \(AB(3)\) is rejected because \(A\) and \(B\) are already connected through \(X\), then add \(BC(4)\). The MST is \(\{AX, XB, BC\}\), which does not contain \(AB\) even though \(AB\) was the smallest edge in its cycle. So Option B is false.

Step 4: Check Option C (leaf vertex counterexample). Let vertex \(v\) have degree 1, connected only by one edge, say of large weight 100. This single edge is simultaneously the largest (and smallest) weight edge incident on \(v\), yet it must be included in the MST because it is the only way to connect \(v\) to the rest of the tree. This directly contradicts the claim that the largest incident edge is never in any MST, so Option C is false.

Step 5: Check Option D (Cut Property). For any vertex \(v\), consider the cut \((\{v\}, V-\{v\})\). Every edge incident on \(v\) crosses this cut, and no other edge of \(G\) does. The Cut Property guarantees that the minimum weight edge crossing any cut belongs to every MST. Since weights are unique, this minimum-weight crossing edge is exactly the smallest weight edge incident on \(v\), so it is forced into the (unique) MST. Hence Option D is true.

Final Answer: \[\boxed{\text{Options A and D are correct}}\]