Exercise 1: Extending the Office MST With a New Storage Room — Possible Solution
====================================================================

GIVEN
------------------------------
This chapter's own Step 3 MST: Lobby-Kitchen(5), Eng-Design(6),
Lobby-Sales(8), Lobby-Eng(12), Eng-Server(15) - total 46m.
New room: Storage, connected ONLY by Design-Storage(7).

STEP 1: RUN KRUSKAL'S ON THE FULL, EXTENDED EDGE LIST
------------------------------
Sorting every edge (including the new one) by weight:
Lobby-Kitchen(5), Eng-Design(6), Design-Storage(7), Lobby-Sales(8),
Lobby-Eng(12), Eng-Server(15), Server-Kitchen(18), Design-Server(20)

Processing in order: Lobby-Kitchen(5) ADD, Eng-Design(6) ADD,
Design-Storage(7) ADD (Storage was in its own component, Design
was not - different components, no cycle), Lobby-Sales(8) ADD,
Lobby-Eng(12) ADD, Eng-Server(15) ADD, then Server-Kitchen(18) and
Design-Server(20) both SKIP (their endpoints are already
connected).

RESULT
------------------------------
New MST: the original five edges, PLUS Design-Storage(7).
New total: 46 + 7 = 53m

WHY THE ORIGINAL FIVE EDGES NEVER NEED RE-EXAMINING
------------------------------
Storage has exactly one possible edge in the entire graph -
Design-Storage(7). Since Storage must be connected to the rest of
the tree somehow (it's still part of the same office), and this is
its ONLY option, that edge is forced into any valid spanning tree
regardless of weight comparisons - there is no competing edge to
even consider. Because Storage is a new LEAF (a vertex with only
one edge), adding it can never create a cheaper alternative route
between any two of the ORIGINAL six rooms - Design-Storage doesn't
connect Design to anything already reachable through the existing
five edges except Storage itself. Kruskal's own correctness
argument from Chapter 8 guarantees each of the five original edges
was the cheapest available way to connect its two components at
the moment it was added, and nothing about a new leaf hanging off
Design changes any of those earlier decisions.

WHY THIS WORKS AS AN ANSWER
------------------------------
The new MST is verified by re-running Kruskal's algorithm on the
full extended edge list from scratch (not just assumed), confirming
the original five edges are unchanged, and the "why" explanation is
grounded in the specific structural fact that Storage is a single-
edge leaf rather than a generic claim that "adding an edge is always
safe."