Question 49

Let $G = K_4$ have 4 vertices $\{A, B, C, D\}$ and 6 edges with weights $\{1, 2, 3, 4, 5, 6\}$. Any spanning tree of $K_4$ contains exactly $4 - 1 = 3$ edges.

Trace Kruskal's algorithm on the sorted edges:

1. The edge with weight 1 is always chosen first (no cycle possible with 1 edge).
2. The edge with weight 2 is always chosen second (no cycle possible with 2 edges in a simple graph).

To maximize the total weight of the MST, we want Kruskal's algorithm to reject the smaller remaining weights (such as 3) so that heavier edges are forced into the tree.

Can the edge of weight 3 be rejected?
Yes! If edges of weights 1, 2, and 3 form a triangle on vertices $\{A, B, C\}$ (i.e. $w(A, B) = 1, w(B, C) = 2, w(A, C) = 3$), then when edge 3 is considered, $A$ and $C$ are already connected in the same component. Edge 3 forms a cycle and is REJECTED by Kruskal's algorithm.

Now vertices $\{A, B, C\}$ form a connected component. To form a spanning tree, the 4th vertex $D$ must be connected to $\{A, B, C\}$.
The 3 edges incident on $D$ must take the remaining weights $\{4, 5, 6\}$.
Kruskal will choose the smallest available edge connecting $D$ to the existing tree, which has weight 4.

The edges in the resulting MST are $\{1, 2, 4\}$.