Let G be a complete undirected graph on 4 vertices, having 6 edges with…

Concept

A spanning tree of a connected graph on n vertices is a cycle-free subgraph that connects all n vertices using exactly n - 1 edges. A minimum spanning tree (MST) is the spanning tree of smallest total weight, and Kruskal's algorithm builds it by scanning edges from smallest weight to largest, adding an edge only if it joins two vertices that are not yet connected.

Cycle test (this answers the reported doubt): an edge creates a cycle precisely when both of its endpoints already lie in the SAME connected component formed by the edges chosen so far. We track components with a union-find (disjoint-set) structure: before adding an edge, ask whether its two endpoints share the same set root; if they do, adding the edge would close a loop, so it is skipped; if they differ, the edge is safe and we merge the two sets.

Here the question is a maximisation over assignments: the six weights 1, 2, 3, 4, 5, 6 are not fixed to particular edges, so we may place them on the edges of the complete graph K4 to make the resulting MST as heavy as possible, then report that largest achievable MST weight.

Application

K4 has 4 vertices and 6 edges, so every spanning tree uses exactly 4 - 1 = 3 edges. To force the MST to keep heavier edges, we arrange the three smallest weights so they form a triangle among three of the vertices; Kruskal then has to discard one of them as a cycle, pulling in a heavier edge instead.

1. Place weights 1, 2 and 3 on the three edges of one triangle, say on vertices A, B, C: edge A-B = 1, edge B-C = 2, edge A-C = 3.

2. Kruskal scans in increasing order. It adds weight 1 (A-B): A and B are in different sets, so they merge.

3. It adds weight 2 (B-C): C is in a different set from {A, B}, so it joins; now {A, B, C} is one component.

4. It examines weight 3 (A-C): both A and C are already in the same component, so this edge would close a cycle and is skipped.

5. The fourth vertex D is still unconnected, so the next smallest edge touching D is forced in. The smallest weight we can place on a D-edge is 4, giving D a connection of weight 4.

6. Three safe edges are now chosen (1, 2 and 4) and all four vertices are connected, so the tree is complete with total weight 1 + 2 + 4 = 7.

Cross-check

Could a heavier MST exist? Whatever the assignment, Kruskal must take the weight-1 edge first (it can never form a cycle on its own) and the weight-2 edge second (two edges on four vertices cannot yet form a cycle). The third chosen edge is at best the weight-4 edge, because the weight-3 edge can be neutralised only by making 1, 2, 3 a triangle, which is exactly what we did. So no assignment beats 1 + 2 + 4. The maximum possible MST weight is therefore 7.

• Larger sums like 15 (4 + 5 + 6) are impossible because Kruskal is always forced to take the weight-1 and weight-2 edges before any of the largest weights.

• Summing all six edges (21) or near-total values describes the whole graph, not a 3-edge tree, so they overcount.