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

This question tests whether you can apply the two core greedy-exchange arguments behind MST correctness, rather than just recalling Kruskal's or Prim's algorithm steps.

Angle: think in terms of exclusion rule vs inclusion rule.

There are exactly two safe rules for building a unique MST when all weights are distinct:
1) Exclusion rule (Cycle Property): in any cycle, the heaviest edge is redundant, because swapping it for a lighter edge of the same cycle only reduces total weight. So statement A, which is exactly this rule, must be true.
2) Inclusion rule (Cut Property): across any cut of the graph, the lightest crossing edge is mandatory, because leaving it out and using a heavier crossing edge instead only increases total weight. Applying this to the trivial cut that isolates a single vertex \(v\) from the rest of the graph, the lightest edge touching \(v\) is the lightest edge crossing that cut, so statement D must be true as well.

Now test the two 'reversed' statements, which are common traps:
Statement B claims the lightest edge of every cycle is always kept. Build a small graph: \(A-X=1\), \(X-B=2\), \(A-B=3\), \(B-C=4\), \(C-A=5\). The triangle \(A-B-C\) has weights \(3, 4, 5\), so \(AB=3\) is its lightest edge. But globally, \(A\) and \(B\) already get connected cheaply through \(X\) (path cost \(1+2=3\) using two edges instead of one), so when edge \(AB=3\) is considered it would only close a cycle and gets discarded. The resulting MST is \(\{AX, XB, BC\}\), skipping \(AB\) entirely. So being 'locally smallest' inside one cycle does not guarantee MST membership, and statement B is false.

Statement C claims the heaviest edge touching a vertex is always dropped. Pick any degree-1 vertex \(v\): it has just one incident edge, which is trivially both its largest and smallest edge, and that edge is unavoidable because it is \(v\)'s only link to the tree. So the heaviest edge at a vertex can certainly appear in the MST, and statement C is false.

Conclusion: only the Cycle Property statement (A) and the Cut Property statement (D) hold in general.

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