Correct : G

Given:
An undirected simple graph G = (V, E) with distinct edge weights.
An edge e ∈ E.
Statement I: If e is the lightest edge of some cycle in G, then every MST of G includes e.
Statement II: If e is the heaviest edge of some cycle in G, then every MST of G excludes e.
To find:
Which of the statements I and II is/are TRUE.
Solution:
Let me analyze Statement I first.
Can an edge be the lightest edge in one cycle, but still get excluded from the MST?
Let me try to construct a counterexample with 4 vertices: A, B, C, and D.
Let the edges and their weights be:
(A, C) = 1
(B, C) = 2
(A, B) = 10
(B, D) = 20
(A, D) = 30
Now consider the cycle A-B-D-A with edge weights 10, 20, and 30.
In this cycle, the edge (A, B) with weight 10 is indeed the lightest edge.
Now let me find the unique MST of this entire graph.
Using Kruskal's algorithm, picking edges in increasing order of weight:
Pick (A, C) of weight 1.
Pick (B, C) of weight 2.
Next smallest edge is (A, B) of weight 10, but adding it forms a cycle A-B-C-A, so discard it.
Pick (B, D) of weight 20.
All 4 vertices are now connected, so the MST consists of edges {(A, C), (B, C), (B, D)}.
The edge (A, B) is not present in the MST, even though it was the lightest edge in cycle A-B-D-A.
So Statement I is FALSE.
Now let me analyze Statement II.
This directly relates to the standard Cycle Property of Minimum Spanning Trees.
According to the Cycle Property, for any cycle in a graph, the strictly heaviest edge in that cycle cannot belong to any MST.
Since all edge weights in G are given to be distinct, the heaviest edge of any cycle is strictly greater than all other edges in that cycle.
If this heaviest edge were part of an MST, replacing it with any other edge of the cycle that connects the two resulting components would yield a spanning tree with a strictly smaller weight, which contradicts the minimality of the MST.
Therefore, e can never be a part of any MST.
So Statement II is TRUE.
Answer:
(B) II only