Project ForgeA connected undirected graph on 6 labeled vertices A, B, C, D, E, F has exactly 8 distinct-integer-weight edges. Its minimum spanning tree (MST) has weight 36, using the 5 edges {(A,C)=9, (B,C)=2, (B,E)=15, (E,F)=4, (D,F)=6}. The other 3 edges of the graph are (A,B), (C,D), and (D,E), with unknown but distinct integer weights. What is the minimum possible sum of the weights of all 8 edges of this graph, consistent with the given MST?
- A63
- B66
- 69
- D72
Explanation
By the MST cycle property, each non-tree edge's weight must be strictly greater than every tree edge on the unique tree path between its endpoints (otherwise it would replace that path's maximum edge and produce a cheaper spanning tree). Tree path A–B is A–C–B (edges 9, 2), max = 9, so weight(A,B) ≥ 10 (smallest unused distinct integer above 9) — take 10. Tree path C–D is C–B–E–F–D (edges 2, 15, 4, 6), max = 15, so weight(C,D) ≥ 16 — take 16. Tree path D–E is D–F–E (edges 6, 4), max = 6, so weight(D,E) ≥ 7 — take 7. Minimum total of the 3 unknown edges = 10+16+7 = 33. Total of all 8 edges = MST weight (36) + 33 = 69.
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
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.