Consider the following graph: Which one of the following cannot be the…

Concept

Kruskal’s algorithm considers graph edges in non-decreasing order of weight. Edges with the same weight may be considered in any order.

An edge is added exactly when it joins two different components. Therefore, a lower-weight edge that is still cycle-free must be added before the algorithm reaches any higher-weight edge.

Application

1. In the sequence (d—f), (a—b), (b—f), (d—e), (d—c), the first three added edges have weights 1, 1, and 2.

2. After those three additions, vertex c is not connected to the component containing d, so the weight-2 edge (d—c) would not form a cycle.

3. Kruskal’s algorithm must therefore add (d—c) while processing weight-2 edges, before it considers the weight-3 edge (d—e).

4. The proposed sequence instead places (d—e) before (d—c), so it cannot be produced by Kruskal’s algorithm.

Cross-check and contrast

• (a—b), (d—f), (b—f), (d—c), (d—e) has weight order 1, 1, 2, 2, 3; equal-weight edges are allowed in this order.

• (a—b), (d—f), (d—c), (b—f), (d—e) also has weight order 1, 1, 2, 2, 3; the two weight-2 edges are merely interchanged.

• (d—f), (a—b), (d—c), (b—f), (d—e) has weight order 1, 1, 2, 2, 3; the equal-weight edges are again interchanged.

• (d—f), (a—b), (b—f), (d—e), (d—c) has weight order 1, 1, 2, 3, 2, which conflicts with the mandatory processing order while (d—c) remains cycle-free.

Result: The sequence (d—f), (a—b), (b—f), (d—e), (d—c) cannot be the order of edges added by Kruskal’s algorithm.