Question

Consider a simple undirected weighted graph \(G\), all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of \(G\) is/are TRUE?

• A. The edge with the second smallest weight is always part of any minimum spanning tree of \(G\).
• B. One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of \(G\).
• C. Suppose \( S \subseteq V \) be such that \( S \neq \emptyset \) and \( S \neq V \). Consider the edge with the minimum weight such that one of its vertices is in \( S \) and the other in \( V \setminus S \). Such an edge will always be part of any minimum spanning tree of \( G \).
• D. \( G \) can have multiple minimum spanning trees.

Hint:

When working with minimum spanning trees, remember that the cut property guarantees the inclusion of the minimum weight edge crossing any cut. Distinct edge weights ensure a unique MST.

Answer 1

The Correct Option is A, B, C

Analysis of Statement (A): The second smallest edge must be part of any MST

In Kruskal's algorithm, we sort all edges in increasing order of weight.

• The smallest edge (rank 1) is always chosen because it cannot form a cycle.
• The second smallest edge (rank 2) can only form a cycle if it connects the same two vertices as the smallest edge. However, in a simple graph (no multiple edges), this is impossible.
• Therefore, the second smallest edge will always be selected.

Therefore, Option (A) is true.

---

Analysis of Statement (B): The third and fourth smallest edges could be part of the MST

As we continue the algorithm, the inclusion of edges depends on the graph's cycle structure.

• The third and fourth smallest edges will be included in the MST unless they form a cycle with previously selected edges.
• Since there are cases where they do not form cycles, it is entirely possible for both to be part of the MST.

Therefore, Option (B) is true.

---

Analysis of Statement (C): Minimum weight edge between two subsets $S$ and $V \setminus S$

This is known as the Cut Property of MSTs.

• For any partition of the vertices of a graph into two non-empty subsets $S$ and $V \setminus S$, the edge with the minimum weight that crosses the cut (connects a vertex in $S$ to one in $V \setminus S$) must belong to the MST.

Therefore, Option (C) is true.

---

Analysis of Statement (D): A graph with distinct edge weights can have multiple MSTs

A key theorem in graph theory states that if all edge weights in a connected graph are distinct, then the graph has exactly one unique MST.

• Both Kruskal's and Prim's algorithms will have no ambiguous choices between edges of the same weight, leading to the same result every time.

Therefore, Option (D) is false.

---

Final Answer:

The correct statements are:(A), (B), and (C)