Consider a simple undirected weighted graph G, all of whose edge weights are…

Correct statements:

• The statement that the edge with the second-smallest weight is always part of any minimum spanning tree is true.

• The statement that for any nontrivial vertex set S the minimum-weight edge crossing the cut (S, V\S) belongs to every minimum spanning tree is true (the cut property).

• The claim that one or both of the edges with the third-smallest and fourth-smallest weights must be part of every MST is not guaranteed.

Incorrect statements:

• The claim that the graph can have multiple minimum spanning trees is false under the hypothesis that all edge weights are distinct; distinct weights imply a unique MST.

Reasoning and proofs:

1. Why the second-smallest edge is always in the MST:

   Run Kruskal's algorithm: sort edges by increasing weight and add them if they do not create a cycle. The smallest edge is added first. After only one edge has been chosen, the second-smallest edge cannot form a cycle, so it will be added as well. With distinct weights the MST produced is unique, so this second-smallest edge belongs to every minimum spanning tree.

2. Proof of the cut property (minimum crossing edge belongs to every MST):

   Let S be a nonempty proper subset of vertices and let e be the minimum-weight edge with one endpoint in S and the other in V\S. Suppose, for contradiction, that some minimum spanning tree T does not contain e. Adding e to T creates a cycle. That cycle must include at least one other edge f that also crosses the cut (S, V\S). Because e is the minimum crossing edge, weight(e) < weight(f). Remove f from the cycle and add e; the result is a spanning tree with strictly smaller total weight than T, contradicting the minimality of T. Hence e must lie in every MST.

3. Suppose S ⊆ V be such that S ≠ φ and S ≠ V. Consider the edge with the minimum

   weight such that one of its vertices is in S and the other in V − S. Such an edge will always

   be part of any minimum spanning tree of G.

   This is True. This is a popular and basic property of Minimum Spanning Tree, known as “Cut

   Property.” The cut property is the basis for the algorithms that we consider for the MST

   problem. “Cut Property” and “Cycle Property” are basic theorems in the study of MST, and

   must be understood by all

Notes on the incorrect statements:

• The possibility of multiple different minimum spanning trees arises only when some edge weights are equal. With all weights distinct, the MST is unique.