Consider the following graph: Which one of the following is NOT the sequence…

Answer: The sequence that is NOT possible is (b,e) (e,f) (a,c) (b,c) (f,g) (c,d).

Reasoning (Kruskal's algorithm):

1. List edges in non-decreasing order of weight (group equal weights together). From the graph the relevant small-weight edges are:

2. Smallest: (b,e) with weight 2. Next smallest group: (a,c) and (e,f) (same small weight). Next group: (b,c) and (f,g) (next larger weight). Then the remaining larger edges follow.

3. Kruskal must consider all edges of the smallest weight group before moving to strictly larger weights; within a group of equal-weight edges the algorithm may choose any order, but cycle checks are always enforced when each edge is considered.

Step-by-step simulation (one valid choice of tie-breaking):

• 1) Pick (b,e) — smallest edge; now component {b,e}.

• 2) Consider the equal-weight edges (a,c) and (e,f). If we pick (a,c) first we form component {a,c}; picking (e,f) first would form {e,f}. Either choice is allowed, but both must be considered before any strictly heavier edges.

• 3) After both small-weight edges are handled, we move to the next-weight edges (b,c) and (f,g). Each is added only if it connects two different components; otherwise it is skipped to avoid a cycle.

• 4) Continue until all vertices are connected; an MST has 6 edges for 7 vertices.

Why the given sequence is impossible (brief):

The sequence (b,e) (e,f) (a,c) (b,c) (f,g) (c,d) attempts to place edges in an order that conflicts with the required processing and cycle checks of Kruskal. In particular, after the necessary small-weight edges have been processed, adding (b,c) at that exact point would either (a) be considered before all equal-weight smaller edges are handled or (b) create a cycle and therefore be skipped by Kruskal. Because Kruskal never adds an edge that creates a cycle and always processes edges in non-decreasing weight order, the exact ordering in this sequence cannot occur.

Summary: The other three sequences can all be realized by choosing different allowable tie-break orders among equal-weight edges while respecting cycle checks; the sequence above cannot.