Project ForgeSign up free
Discrete Mathematics
Graph Theory
GATE 2016
Expert

Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum spanning tree of G can have is ____.

7

Explanation

By the cut property, the globally smallest-weight edge (1) is ALWAYS in every MST, and — specific to a 4-vertex complete graph — the second-smallest edge (2) is ALSO always includable: after adding edge-weight-1, the graph has 3 components, and no other single edge (being distinct from the weight-1 edge) can possibly close a cycle among only 3 components with just 2 edges placed. So after both are added, exactly 2 components remain, and a 3rd edge is needed to finish the spanning tree. To maximize that 3rd edge's value, arrange weights 1 and 2 to form 2 sides of a triangle among 3 of the 4 vertices (say A-B=1, B-C=2), leaving only ONE more 'wasteable' internal edge (A-C) among the remaining weights {3,4,5,6}; assign that internal edge the smallest remaining weight (3, which Kruskal's algorithm skips as it would form a cycle), leaving the 3 edges connecting the 4th vertex D to get weights {4,5,6} — Kruskal's then picks the smallest of these, 4, to complete the tree. Total MST weight = 1+2+4 = 7. No arrangement can waste more than this one internal edge, so 7 is the true maximum.

Source: GATE CS 2016 (Session 1 / Set A) (2016)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free