# Lecture 11. Graph theory — algorithms ## 11.1 Overview Lecture 10 developed the *static* language of graphs: vertices and edges, degrees, adjacency representations, weighted graphs, and the two coloring invariants — the **chromatic number** $\chi(G)$ (fewest colors for a proper vertex coloring) and the **chromatic index** $\chi'(G)$ (fewest colors for a proper edge coloring). That lecture told us *what* these quantities are; it did not tell us how to *compute* anything. This lecture is about *doing* things with graphs: first the two systematic **traversals** (breadth- and depth-first search) that visit every vertex, then five classical algorithms that produce colorings, shortest paths, and cheapest connecting networks, together with the data structures that make them fast and the proofs that make them trustworthy. Three questions organize the chapter, each drawn from a real computational need. 1. **How do we schedule conflicting tasks with as few resources as possible?** This is graph coloring. We study **greedy vertex coloring** and **greedy edge coloring** — fast, simple heuristics that always produce a *valid* coloring and come with provable upper bounds on how many colors they use. 2. **What is the cheapest way to get from one place to every other place?** This is the single-source shortest-path problem, solved by **Dijkstra's algorithm** when edge weights are non-negative. 3. **What is the cheapest network that keeps everything connected?** This is the minimum spanning tree problem, solved by **Prim's** and **Kruskal's** algorithms — two greedy routes to the same optimum, both justified by a single beautiful lemma, the *cut property*. ### A recurring theme: greed Every *optimization* algorithm in this lecture is **greedy** (the two traversals, BFS and DFS, are the exception): it builds its answer incrementally and, at each step, commits to the choice that looks best *right now*, never reconsidering. Greedy algorithms are attractive because they are simple and fast, but the deep question is always the same: > *Does taking the locally best choice at every step lead to a globally optimal result?* The answer here is instructive precisely because it is **not uniform**: - For **shortest paths and minimum spanning trees**, greedy is *exactly optimal*, and we will prove it — via the "finalized-distance" invariant for Dijkstra and via the *cut property* for Prim and Kruskal. - For **coloring**, greedy is only an *approximation*: it always yields a proper coloring, but may use more colors than the optimum $\chi(G)$ or $\chi'(G)$, and the number it uses depends on the order in which objects are processed. Keeping this contrast in mind — *when* greed is provably safe and *when* it is merely a bounded heuristic — is one of the main takeaways of the lecture. ### Prerequisites and notation We lean on the following from **Lecture 10** (graph basics): - A **weighted graph** attaches a real number $w(u,v)$ — a *weight*, *cost*, *length*, or *capacity* — to each edge. - The **adjacency list** stores, for each vertex $v$, the list of its neighbors together with edge weights. It uses $O(n+m)$ space and lets us scan a vertex's incident edges in time proportional to its degree. **This is the representation assumed throughout.** The alternative adjacency matrix costs $\Theta(n^2)$ space and is only competitive on very dense graphs. - A **proper coloring** never gives the same color to two adjacent objects (adjacent *vertices* for vertex coloring; edges *sharing an endpoint* for edge coloring). - $\Delta = \Delta(G)$ denotes the **maximum degree** of the graph, and $\deg(v)$ the degree of vertex $v$. Recall the **Handshaking Lemma** $\sum_v \deg(v) = 2m$. We write $n = |V|$ for the number of vertices and $m = |E|$ for the number of edges. Inside asymptotic bounds we follow the standard convention (as in CLRS) of writing $V$ and $E$ for these counts, so that "$O(V+E)$" means "$O(n+m)$"; the letters name the sets, but in an $O(\cdot)$ they stand for the sizes. Spanning trees, forests, and the structural theory of trees are the subject of **Lecture 12**; we borrow two facts from there and flag them where used. > The running graph $G$ — defined and drawn in the next section — places $A$ at the far > left, $F$ at the far right, and $B,C$ / $D,E$ as two middle columns, with every edge > labelled by its weight. The single figure is reused for all five algorithms: coloring > ignores the weights, the path/tree algorithms use them. --- ## 11.2 A word on greedy algorithms Before the graph algorithms, it helps to name the pattern they share. **Greedy algorithm** — an algorithm that constructs a solution in a sequence of steps, and at each step irrevocably makes the choice that is locally optimal according to some fixed rule, without backtracking. ![Greedy strategy: take the cheapest option at each step](img/l11_greedy.png) Two ingredients decide whether a greedy algorithm is *correct* (produces a globally optimal answer), rather than merely *fast*: - The **greedy-choice property**: there is always a globally optimal solution that is consistent with the greedy first choice. (For MSTs this is exactly the cut property.) - **Optimal substructure**: an optimal solution to the whole problem contains optimal solutions to subproblems, so that after making the greedy choice, solving the rest greedily still yields the optimum. When both hold, an exchange argument (swap the greedy choice into an arbitrary optimal solution without making it worse) proves optimality. Shortest paths and MSTs enjoy both, which is why Dijkstra, Prim, and Kruskal are *exact*. Coloring lacks the greedy-choice property — the locally cheapest color can paint us into a corner — so greedy coloring is only a bounded approximation. (The deepest reason MST greed works is that the sets of "edges extendable to a spanning tree" form a *matroid*; matroids are exactly the structures on which greedy is always optimal. See *Further reading*.) **Remark.** "Greedy" is a strategy, not a guarantee. The same word covers a provably optimal algorithm (Dijkstra) and a heuristic that can be arbitrarily far from optimal (greedy coloring on a bad ordering). Always ask which case you are in. --- ## 11.3 The running weighted graph To let the results be *compared*, we run Dijkstra, Prim, and Kruskal — and, ignoring the weights, both coloring algorithms — on **one** shared weighted graph $G=(V,E)$. $$ V=\{A,B,C,D,E,F\}, $$ with the nine weighted edges | Edge | $w$ | Edge | $w$ | Edge | $w$ | |:----:|:---:|:----:|:---:|:----:|:---:| | $A\text{–}B$ | 4 | $B\text{–}D$ | 5 | $D\text{–}E$ | 3 | | $A\text{–}C$ | 2 | $C\text{–}D$ | 8 | $D\text{–}F$ | 6 | | $B\text{–}C$ | 1 | $C\text{–}E$ | 10 | $E\text{–}F$ | 7 | As adjacency lists (neighbors with weights): $$ \begin{aligned} A&:\{B(4),\,C(2)\} & B&:\{A(4),\,C(1),\,D(5)\} & C&:\{A(2),\,B(1),\,D(8),\,E(10)\}\\ D&:\{B(5),\,C(8),\,E(3),\,F(6)\} & E&:\{C(10),\,D(3),\,F(7)\} & F&:\{D(6),\,E(7)\} \end{aligned} $$ ![The running weighted graph G on six vertices with its nine labelled edge weights](img/l11_wgraph.png) Degrees are $\deg(A)=2,\ \deg(B)=3,\ \deg(C)=4,\ \deg(D)=4,\ \deg(E)=3,\ \deg(F)=2$, so the maximum degree is $\Delta=4$ and (Handshaking check) $\sum_v\deg(v)=18=2\cdot 9=2m$. The graph is **connected** (needed for the MST algorithms) and its nine weights are **distinct** (which, as we prove later, makes the MST *unique* — so Prim and Kruskal must return the very same edge set, an ideal setup for comparison). It also contains several triangles ($ABC$, $BCD$, $CDE$, $DEF$), which will force at least three colors. --- ## 11.4 Graph traversal: breadth-first and depth-first search Before optimizing over a graph we must be able to **visit** it systematically — reach every vertex, discover the connected component of a start vertex, and build a tree of first-discoveries. The two canonical traversals differ only in the **data structure** that holds the frontier of discovered-but-unexplored vertices: a **queue** gives **breadth-first search (BFS)**, a **stack** (or recursion) gives **depth-first search (DFS)**. ```text BFS(G, s): DFS(G, s): # recursive mark every vertex unvisited mark s visited Q ← queue holding s; visit s for each neighbor w of s: while Q not empty: if w unvisited: u ← dequeue(Q) DFS(G, w) for each neighbor w of u: if w unvisited: visit w; enqueue(Q, w) ``` DFS is usually written recursively — the call stack *is* the stack; an explicit-stack variant simply replaces BFS's queue by a stack. Each vertex is enqueued once and each edge examined a constant number of times, so with adjacency lists both run in $O(|V|+|E|)$ — **linear** in the size of the graph. **Worked trace on $G$ (weights ignored), starting at $A$, neighbors in alphabetical order.** - **BFS** visits $A;\ B,C;\ D,E;\ F$ in *rings* of increasing distance from $A$. Its tree of discovery edges is $\{AB,AC,BD,CE,DF\}$, and the ring number is exactly the **fewest-edges distance** from $A$: $A{=}0,\ B{=}1,\ C{=}1,\ D{=}2,\ E{=}2,\ F{=}3$. - **DFS** plunges $A\to B\to C\to D\to E\to F$, backtracking only at dead ends; its discovery tree is the **path** $\{AB,BC,CD,DE,EF\}$. Same vertices, different trees — BFS stays shallow and wide, DFS goes deep. **What traversal is for.** - **Connectivity and components.** One traversal reaches exactly the start vertex's component; restarting from any still-unvisited vertex counts the **connected components** (§10.9) in $O(|V|+|E|)$. - **Shortest paths in an *unweighted* graph.** BFS's ring number is the minimum number of edges from the source — the unweighted counterpart of Dijkstra below, and far cheaper when the weights are all equal. - **Paths and cycles.** DFS underlies path-finding, cycle detection, and topological ordering; the `findPath`/`findCircuit` routines of Lab 6 are DFS at heart. Traversal is the workhorse the rest of this chapter leans on: Dijkstra's and Prim's frontier-growing loops are BFS with a **priority** queue in place of a plain one. --- ## 11.5 Greedy vertex coloring ### Motivation Vertex coloring is the abstract form of **conflict scheduling**. Model each task as a vertex and join two tasks by an edge when they *conflict* (cannot share a resource). A proper coloring is then an assignment of resources — exam time slots, radio frequencies, CPU registers — such that no two conflicting tasks collide, and the number of colors is the number of resources needed. The classic compiler application is **register allocation**: variables are vertices, an edge means two variables are "live" simultaneously, colors are machine registers. Finding $\chi(G)$ exactly is **NP-hard**, so in practice we reach for a fast heuristic. The simplest is greedy. ### The algorithm **Greedy vertex coloring** — fix an ordering $v_1, v_2, \dots, v_n$ of the vertices; visit them in that order and give each vertex the smallest color (a positive integer $1, 2, 3, \dots$) not already used by any of its *already-colored* neighbors. ``` function GreedyVertexColoring(G, ordering v1..vn): for i = 1 to n: used ← { color[u] : u is a neighbor of vi and u already colored } color[vi] ← smallest positive integer not in used return color ``` **Finding the smallest free color efficiently.** Naively "scanning for a gap" sounds like it could be slow, but it is not. Keep a scratch boolean array `seen[1..Δ+1]`. When coloring $v_i$, for each already-colored neighbor $u$ with $\text{color}[u]\le \deg(v_i)+1$ set `seen[color[u]] ← true`; then scan $c = 1,2,\dots$ for the first index with `seen[c] = false`. Because $v_i$ has at most $\deg(v_i)$ colored neighbors, the answer is at most $\deg(v_i)+1$, so the scan stops within $\deg(v_i)+1$ steps. Reset only the entries you touched (or use a version-stamp trick) so the per-vertex cost stays $O(\deg(v_i))$. ### Worked trace Run greedy on $G$ (ignoring weights) in the natural order $A,B,C,D,E,F$. The "colored neighbors" column lists each neighbor that is *already* colored and its color. | Step | Vertex | Colored neighbors (colors) | Forbidden colors | Assigned | |:----:|:------:|:---------------------------|:----------------:|:--------:| | 1 | $A$ | — | $\{\}$ | **1** | | 2 | $B$ | $A(1)$ | $\{1\}$ | **2** | | 3 | $C$ | $A(1),\,B(2)$ | $\{1,2\}$ | **3** | | 4 | $D$ | $B(2),\,C(3)$ | $\{2,3\}$ | **1** | | 5 | $E$ | $C(3),\,D(1)$ | $\{1,3\}$ | **2** | | 6 | $F$ | $D(1),\,E(2)$ | $\{1,2\}$ | **3** | Colors used: $\{1,2,3\}$ — three colors. The final coloring is $A{=}1,\ B{=}2,\ C{=}3,\ D{=}1,\ E{=}2,\ F{=}3$; a quick check of all nine edges confirms every edge joins two differently colored endpoints, so it is *proper*. Is three optimal? Yes: the triangle $A\text{–}B\text{–}C$ has three mutually adjacent vertices, all of which need distinct colors, so $\chi(G)\ge 3$; and greedy exhibited a proper $3$-coloring, so $\chi(G)=3$ and here greedy is *optimal*. ### Correctness: greedy always produces a proper coloring **Theorem 11.1.** For every graph $G$ and every vertex ordering, `GreedyVertexColoring` returns a proper coloring. *Proof.* Take any edge $uv \in E$; we must show $\text{color}[u]\ne\text{color}[v]$. Without loss of generality $u$ is colored before $v$ (one of them is). At the moment $v$ is colored, $u$ is an *already-colored neighbor* of $v$, so $\text{color}[u]$ lies in the set `used` that $v$ avoids. Hence $\text{color}[v]\ne\text{color}[u]$. As $uv$ was arbitrary, no edge is monochromatic. $\square$ ### Correctness: the $\Delta+1$ bound **Theorem 11.2.** `GreedyVertexColoring` uses at most $\Delta+1$ colors, for every ordering. Consequently $\chi(G)\le \Delta+1$. *Proof.* When vertex $v_i$ is colored, the forbidden set `used` is contained in the set of colors of $v_i$'s already-colored neighbors, so $|\texttt{used}| \le \deg(v_i)\le\Delta$. Among the $\Delta+1$ colors $\{1,2,\dots,\Delta+1\}$ at most $\Delta$ are forbidden, so at least one is free; greedy picks the smallest free color, which is therefore $\le\Delta+1$. No vertex ever receives a color exceeding $\Delta+1$, so the total number of colors used is $\le\Delta+1$. Since the coloring is proper (Theorem 11.1), $\chi(G)\le\Delta+1$. $\square$ On $G$, $\Delta=4$, so the theorem promises $\le 5$ colors; greedy did much better with $3$ because the ordering was favorable. **Remark (Brooks' theorem).** The bound $\Delta+1$ is rarely tight. *Brooks' theorem* (1941) states that a connected graph satisfies $\chi(G)\le\Delta$ *unless* $G$ is a complete graph $K_n$ (which needs $n=\Delta+1$) or an odd cycle (which needs $3=\Delta+1$). Our $G$ is neither, and indeed $\chi(G)=3\le\Delta=4$. ### The ordering matters Theorem 11.2 bounds the *worst case*, but the *actual* number of colors depends heavily on the processing order. Greedy is always proper, yet the color count is not. **A concrete gap on $G$.** Run greedy on the *same* graph $G$ in the order $A,E,B,D,C,F$: | Step | Vertex | Colored neighbors (colors) | Assigned | |:----:|:------:|:---------------------------|:--------:| | 1 | $A$ | — | **1** | | 2 | $E$ | — (none of $C,D,F$ colored yet) | **1** | | 3 | $B$ | $A(1)$ | **2** | | 4 | $D$ | $B(2),\,E(1)$ | **3** | | 5 | $C$ | $A(1),\,B(2),\,D(3),\,E(1)$ | **4** | | 6 | $F$ | $D(3),\,E(1)$ | **2** | This uses **four** colors, although $\chi(G)=3$. The culprit is vertex $C$: by the time it is reached, its four neighbors already carry three distinct colors $\{1,2,3\}$, forcing a fourth. Same graph, same algorithm, different order — one extra color. **A dramatic gap: the crown graph.** The **crown graph** $S_n^0$ is $K_{n,n}$ with a perfect matching deleted: parts $\{x_0,\dots,x_{n-1}\}$ and $\{y_0,\dots,y_{n-1}\}$, with $x_i$ adjacent to every $y_j$ *except* $y_i$. It is bipartite, so $\chi=2$. But process the vertices in the paired order $x_0,y_0,x_1,y_1,\dots,x_{n-1},y_{n-1}$: an easy induction shows $x_k$ and $y_k$ each see exactly the colors $\{1,\dots,k\}$ on already-colored neighbors and so receive color $k+1$. Greedy therefore uses $n$ colors on $2n$ vertices — arbitrarily far from the true value $2$. (For $n=3$ this already forces $3$ colors instead of $2$.) There is *always* an ordering achieving the optimum $\chi(G)$ — color the vertices in the order an optimal coloring would — but finding such an order is as hard as coloring itself. ### The Welsh–Powell heuristic Since order is everything, a good default is to color high-degree vertices first, on the intuition that they are the hardest to satisfy and should be handled while colors are plentiful. **Welsh–Powell coloring** — sort the vertices in *non-increasing* order of degree, then run greedy in that order. ``` function WelshPowell(G): sort vertices so that deg(v1) ≥ deg(v2) ≥ … ≥ deg(vn) return GreedyVertexColoring(G, v1..vn) ``` On $G$ the degrees are $C{:}4,\ D{:}4,\ B{:}3,\ E{:}3,\ A{:}2,\ F{:}2$, giving the order $C,D,B,E,A,F$: | Step | Vertex | Colored neighbors (colors) | Assigned | |:----:|:------:|:---------------------------|:--------:| | 1 | $C$ | — | **1** | | 2 | $D$ | $C(1)$ | **2** | | 3 | $B$ | $C(1),\,D(2)$ | **3** | | 4 | $E$ | $C(1),\,D(2)$ | **3** | | 5 | $A$ | $B(3),\,C(1)$ | **2** | | 6 | $F$ | $D(2),\,E(3)$ | **1** | Three colors — optimal. Welsh–Powell also yields the useful bound $\chi(G)\le \max_i \min\{\,d_i+1,\ i\,\}$, where $d_1\ge d_2\ge\cdots$ is the sorted degree sequence and $i$ is the position. It is a *heuristic*, not a guarantee: there exist graphs where even largest-degree-first is suboptimal. But it is cheap and usually good. ### Complexity and data structures **Data structure:** adjacency lists plus one reusable scratch array `seen[1..Δ+1]`. **Time:** for each vertex $v_i$ we do $O(\deg(v_i))$ work (mark neighbor colors, scan for the first gap, reset). Summing over all vertices and using the Handshaking Lemma, $$ \sum_{i=1}^{n} O(\deg(v_i)) = O\!\Big(n + \sum_v \deg(v)\Big) = O(n + 2m) = O(V+E). $$ Welsh–Powell adds an $O(V\log V)$ sort, giving $O(V\log V + E)$. **Space** is $O(V)$ beyond the graph itself. **Common pitfall.** Do *not* believe that greedy computes $\chi(G)$. It computes *a* proper coloring whose size is between $\chi(G)$ and $\Delta+1$, and which depends on the ordering. If you need the true chromatic number you must search (exponential in the worst case). **CS connection.** Chaitin's classic register allocator (1981) models allocation as vertex coloring of an *interference graph* and colors it greedily; when more than $k$ colors (= registers) are needed, some variable is "spilled" to memory — the practical response to greedy's non-optimality. --- ## 11.6 Greedy edge coloring ### Motivation Edge coloring is the natural model for **timetabling round-robin schedules**. Represent players (or teams, machines, people) as vertices and each required match/meeting as an edge; a color is a *time slot*. Two edges sharing an endpoint must get different colors (a player cannot play two matches at once), so a proper edge coloring is a conflict-free schedule and $\chi'(G)$ is the fewest time slots needed. ### The algorithm **Greedy edge coloring** — fix an ordering of the edges; give each edge the smallest color not used by any *adjacent* edge (an edge that shares an endpoint) that is already colored. ``` function GreedyEdgeColoring(G, ordering e1..em): for k = 1 to m: let ek = (u, v) used ← { color[e] : e already colored and e shares endpoint u or v with ek } color[ek] ← smallest positive integer not in used return color ``` This is *literally* greedy vertex coloring run on the **line graph** $L(G)$, whose vertices are the edges of $G$ and whose edges join pairs of $G$-edges that share an endpoint. Every theorem about greedy vertex coloring transfers, with $\Delta(L(G))$ in place of $\Delta(G)$. ### Worked trace Color $G$ processing edges in the order $AB, AC, BC, BD, CD, CE, DE, DF, EF$. Recall $\Delta(G)=4$. | Step | Edge | Adjacent colored edges (colors) | Assigned | |:----:|:----:|:--------------------------------|:--------:| | 1 | $AB$ | — | **1** | | 2 | $AC$ | $AB(1)$ | **2** | | 3 | $BC$ | $AB(1),\,AC(2)$ | **3** | | 4 | $BD$ | $AB(1),\,BC(3)$ | **2** | | 5 | $CD$ | $AC(2),\,BC(3),\,BD(2)$ | **1** | | 6 | $CE$ | $AC(2),\,BC(3),\,CD(1)$ | **4** | | 7 | $DE$ | $BD(2),\,CD(1),\,CE(4)$ | **3** | | 8 | $DF$ | $BD(2),\,CD(1),\,DE(3)$ | **4** | | 9 | $EF$ | $CE(4),\,DE(3),\,DF(4)$ | **1** | Four colors. The four **color classes** are $$ 1:\{AB,CD,EF\}\quad 2:\{AC,BD\}\quad 3:\{BC,DE\}\quad 4:\{CE,DF\}, $$ and each is a **matching** (no two of its edges share a vertex; the formal treatment and Hall's theorem are in Lecture 12 §12.9) — which is exactly what "proper edge coloring" means. Class $1$ is even a *perfect* matching, pairing up all six vertices. Since $\chi'(G)\ge\Delta=4$ (the four edges at $C$ must all differ), greedy's four colors are *optimal* here: $\chi'(G)=4$. ### Correctness and bounds **Theorem 11.3 (proper).** `GreedyEdgeColoring` always returns a proper edge coloring. *Proof.* It is Theorem 11.1 applied to the line graph $L(G)$: two edges sharing an endpoint are adjacent vertices of $L(G)$, and the algorithm gives them different colors by the same argument. $\square$ **Theorem 11.4 (the $2\Delta-1$ bound).** `GreedyEdgeColoring` uses at most $2\Delta-1$ colors. *Proof.* An edge $e=uv$ is adjacent to at most $(\deg u-1)+(\deg v-1)\le 2\Delta-2$ other edges, hence to at most $2\Delta-2$ *already-colored* ones. Among the colors $\{1,\dots,2\Delta-1\}$ at least one is free, and greedy takes the smallest such. $\square$ How good is $2\Delta-1$? Compare it with the optimum, pinned down by a famous theorem from Lecture 10. **Vizing's theorem.** Every simple graph satisfies $\chi'(G)\in\{\Delta,\ \Delta+1\}$. So the true optimum is one of just *two* values, whereas greedy only promises $2\Delta-1$ — off by nearly a factor of two in the worst case. On $G$ greedy happened to hit the optimum $\Delta=4$, but in general greedy edge coloring is a weaker approximation than the theory allows. ### Complexity **Data structure:** adjacency lists plus a scratch array of size $2\Delta$. **Time:** for edge $e=uv$ we scan its $\le 2\Delta-2$ adjacent edges and find the smallest free color in $O(\Delta)$. Summed over all edges, $$ \sum_{uv\in E}\big(\deg u+\deg v\big) = \sum_v \deg(v)^2 \le \Delta\sum_v\deg(v)=2\Delta m, $$ so the total is $O(E\cdot\Delta)$. **Space** $O(V+E)$. **Common pitfall.** "Adjacent" for edge coloring means *sharing an endpoint*, not *being consecutive in the input list*. An edge must avoid the colors of edges at **both** of its endpoints. --- ## 11.7 Dijkstra's shortest-path algorithm ### Motivation and the problem Given a weighted graph and a start vertex, we want the cheapest route to everywhere else: the **single-source shortest-path problem**. This is the computational core of GPS navigation, packet routing (the link-state protocol OSPF runs Dijkstra), network latency analysis, and countless planning tasks. **Shortest-path distance** — write $\delta(s,v)$ for the minimum weight of any path from the source $s$ to $v$ (and $\delta(s,v)=\infty$ if $v$ is unreachable). A **shortest path** is a path achieving this minimum. **Dijkstra's algorithm** finds $\delta(s,v)$ for every $v$ in a graph whose edge weights are all **non-negative**. It maintains a **tentative distance** $\text{dist}[v]$ for each vertex — the length of the best route to $v$ found *so far* — repeatedly **finalizes** the unfinished vertex of smallest tentative distance, and then **relaxes** that vertex's edges. **Relaxation** — for an edge $(u,v)$: if $\text{dist}[u] + w(u,v) < \text{dist}[v]$, a shorter route to $v$ *through* $u$ has been found, so update $\text{dist}[v] \leftarrow \text{dist}[u] + w(u,v)$ and set $\text{prev}[v]\leftarrow u$ (recording the predecessor, so paths can be reconstructed). ### Pseudocode ``` function Dijkstra(G, w, s): for each vertex v in G: dist[v] ← ∞ prev[v] ← undefined dist[s] ← 0 Q ← min-priority queue of all vertices, keyed by dist while Q is not empty: u ← extract-min(Q) # closest not-yet-finalized vertex for each neighbor v of u: alt ← dist[u] + w(u, v) if alt < dist[v]: # relaxation dist[v] ← alt prev[v] ← u decrease-key(Q, v, alt) return dist, prev ``` Once a vertex is extracted from $Q$, its distance is **final** and never changes again — the crux of the correctness proof below. ### Worked trace Run Dijkstra on $G$ from source $A$. Each row shows the tentative-distance array *after* one more vertex has been finalized; the **Chosen** column names the vertex just extracted (with its now-final distance), and a dash "$-$" means "not yet reached" ($\infty$). | Step | Chosen | $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | |:----:|:------:|:---:|:---:|:---:|:---:|:---:|:---:| | 0 (init) | — | 0 | $-$ | $-$ | $-$ | $-$ | $-$ | | 1 | $A\,(0)$ | 0 | 4 | 2 | $-$ | $-$ | $-$ | | 2 | $C\,(2)$ | 0 | **3** | 2 | 10 | 12 | $-$ | | 3 | $B\,(3)$ | 0 | 3 | 2 | **8** | 12 | $-$ | | 4 | $D\,(8)$ | 0 | 3 | 2 | 8 | **11** | 14 | | 5 | $E\,(11)$ | 0 | 3 | 2 | 8 | 11 | 14 | | 6 | $F\,(14)$ | 0 | 3 | 2 | 8 | 11 | 14 | Reading the steps (bold entries mark a *strict improvement* by relaxation): - **Step 1** — extract $A$ (dist $0$); relax its edges, giving $B=4$ and $C=2$. - **Step 2** — the smallest tentative distance is $C=2$; finalize it and relax $C$'s edges. Edge $C\text{–}B$ gives $2+1=3<4$, so **$B$ improves from $4$ to $3$** (the route $A\to C\to B$ beats the direct edge $A\to B$). Also $D=2+8=10$ and $E=2+10=12$. - **Step 3** — extract $B=3$; relax $B\text{–}D$: $3+5=8<10$, so **$D$ improves to $8$** (route $A\to C\to B\to D$). ($B$'s only neighbors are $A,C,D$, so $E$ is untouched here.) - **Step 4** — extract $D=8$; relax $D\text{–}E$: $8+3=11<12$, so **$E$ improves to $11$**; relax $D\text{–}F$: $F=8+6=14$. - **Step 5** — extract $E=11$; relax $E\text{–}F$: $11+7=18 > 14$, **no improvement** — the longer route is correctly rejected. - **Step 6** — extract $F=14$; nothing left to improve. Done. Final distances from $A$: $A{=}0,\ B{=}3,\ C{=}2,\ D{=}8,\ E{=}11,\ F{=}14$. Three separate vertices ($B$, $D$, $E$) had their distances improved *after* first being reached — the essence of relaxation — and $F$'s tempting-but-worse route through $E$ was discarded. **Path reconstruction.** Follow $\text{prev}$ backward from the target. For $F$: $\text{prev}[F]=D,\ \text{prev}[D]=B,\ \text{prev}[B]=C,\ \text{prev}[C]=A$, giving the shortest path $A\to C\to B\to D\to F$ of length $2+1+5+6=14$. The $\text{prev}$ pointers of all vertices together form the **shortest-path tree** rooted at $A$. ![Shortest-path tree from A (highlighted) on the running graph; farthest vertex F at distance 14](img/l11_dijkstra_tree.png) ### Correctness Two elementary facts first, then the main theorem. **Lemma A (upper-bound property).** At all times $\text{dist}[v]\ge\delta(s,v)$, and once $\text{dist}[v]$ is finite it is the length of *some* actual $s$–$v$ path. *Proof.* Initially $\text{dist}[s]=0=\delta(s,s)$ and all others are $\infty$. Relaxation only ever sets $\text{dist}[v]=\text{dist}[u]+w(u,v)$, which is the length of the path to $u$ (a real path, inductively) extended by edge $(u,v)$; and no real path can be shorter than the minimum $\delta(s,v)$. $\square$ **Lemma B (subpath optimality).** If $s=x_0,x_1,\dots,x_k$ is a shortest path, then each prefix $x_0,\dots,x_j$ is a shortest path to $x_j$, so $\delta(s,x_j)+w(x_j,x_{j+1})= \delta(s,x_{j+1})$. *Proof.* A cheaper route to a prefix endpoint could be spliced in to beat the whole path, contradicting its optimality. $\square$ **Theorem 11.5 (Dijkstra correctness).** When Dijkstra extracts a vertex $u$ from $Q$, its distance is correct: $\text{dist}[u]=\delta(s,u)$. Hence all final distances are correct. *Proof (by contradiction on the extraction order).* Suppose not, and let $u$ be the **first** vertex extracted with $\text{dist}[u]\ne\delta(s,u)$. By Lemma A, $\text{dist}[u]\ge \delta(s,u)$, so in fact $\text{dist}[u]>\delta(s,u)$. Note $u\ne s$ (since $\text{dist}[s]=0 =\delta(s,s)$ and $s$ is extracted first, correctly), and $\delta(s,u)<\infty$ (otherwise $\text{dist}[u]=\infty=\delta(s,u)$), so a shortest path $P$ from $s$ to $u$ exists. Let $S$ be the set of vertices already finalized (extracted) just before $u$ is extracted. Then $s\in S$ but $u\notin S$, so $P$ starts inside $S$ and ends outside it. Walk along $P$ and let $y$ be the **first** vertex on $P$ that is *not* in $S$, and let $x$ be its predecessor on $P$ (so $x\in S$; possibly $x=s$). *Claim: $\text{dist}[y]=\delta(s,y)$.* Since $x\in S$, $x$ was extracted **before** $u$, and by our choice of $u$ as the first bad vertex, $\text{dist}[x]=\delta(s,x)$ held at $x$'s extraction. At that moment we relaxed edge $(x,y)$, so afterward $\text{dist}[y]\le\text{dist}[x]+w(x,y)=\delta(s,x)+w(x,y)$. By Lemma B (as $x,y$ are consecutive on the shortest path $P$), $\delta(s,x)+w(x,y)=\delta(s,y)$. Thus $\text{dist}[y]\le\delta(s,y)$, and with Lemma A, $\text{dist}[y]=\delta(s,y)$, proving the claim. Now $y$ lies on $P$ at or before $u$, and the piece of $P$ from $y$ to $u$ has **non-negative** total weight (this is the *only* place non-negativity is used!), so $\delta(s,y)\le\delta(s,u)$. Chaining the (in)equalities, $$ \text{dist}[y]=\delta(s,y)\le\delta(s,u)<\text{dist}[u]. $$ But both $y$ and $u$ are in $Q$ when the algorithm chose to extract $u$ by **minimum** tentative distance, forcing $\text{dist}[u]\le\text{dist}[y]$ — contradicting $\text{dist}[y]<\text{dist}[u]$. No such $u$ exists, so every extraction is correct. $\square$ **Why non-negativity is essential.** The single step $\delta(s,y)\le\delta(s,u)$ assumes the $y\to u$ portion of $P$ costs $\ge 0$. A negative edge breaks this, and Dijkstra can finalize a vertex too early. **Common pitfall — negative weights.** Consider the *directed* graph $A\to B$ ($w=2$), $A\to C$ ($w=3$), $C\to B$ ($w=-2$). Dijkstra extracts $A$, sets $\text{dist}[B]=2,\ \text{dist}[C]=3$, then extracts and **finalizes $B$ at $2$** (it is the smallest), before ever examining $C$. But the true shortest route is $A\to C\to B$ with length $3+(-2)=1$. Dijkstra never revisits a finalized vertex, so it reports $\text{dist}[B]=2$ — *wrong*. (If $B$ had any outgoing edge, the premature value $2$ would propagate, corrupting descendants too.) For graphs with negative edge weights use the **Bellman–Ford algorithm**, which relaxes *every* edge $V-1$ times in $O(VE)$ and, on a $V$-th pass that still improves something, detects a **negative-weight cycle** (on which no shortest path exists). ### Complexity The running time depends entirely on the priority queue. Let $T_{\text{ex}}$ and $T_{\text{dk}}$ be the costs of extract-min and decrease-key. There are $V$ extractions and at most $E$ decrease-keys (one per relaxation), giving $O(V\cdot T_{\text{ex}} + E\cdot T_{\text{dk}})$. | Priority queue | extract-min | decrease-key | Total | Best for | |:---------------|:-----------:|:------------:|:------|:---------| | Binary (min-)heap | $O(\log V)$ | $O(\log V)$ | $O((V+E)\log V)=O(E\log V)$ | general/sparse | | Unsorted array | $O(V)$ | $O(1)$ | $O(V^2+E)=O(V^2)$ | dense ($E\!\approx\!V^2$) | | Fibonacci heap | $O(\log V)$* | $O(1)$* | $O(E+V\log V)$ | theory / very large sparse | (*amortized.) The workhorse is the **binary heap**, an array-embedded complete binary tree in which every node's key is $\le$ its children's; `insert`, `decrease-key`, and `extract-min` each cost $O(\log V)$ by sifting an element up or down one tree level at a time. For a *connected* graph $E\ge V-1$, so $O((V+E)\log V)=O(E\log V)$. **Remark (lazy deletion).** Many implementations skip `decrease-key`: on each relaxation they simply push a *new* $(\text{dist},v)$ pair and, on extraction, discard any pair whose key exceeds the current $\text{dist}[v]$. The heap may hold up to $E$ entries, but since $\log E\le\log V^2=2\log V$, the bound is still $O(E\log V)$. This trades a little memory for much simpler code and is what most standard libraries do. **Common pitfall.** Do not "update in place then forget to re-heapify." Either call a real `decrease-key`, or use lazy deletion and check for stale entries at extraction — otherwise the queue's min is wrong. **CS connection.** Dijkstra is the basis of link-state routing (OSPF, IS-IS) and of the "uniform-cost search" in AI; adding a goal-directed heuristic turns it into the **A\*** search algorithm used in games and mapping. --- ## 11.8 Minimum spanning trees and the cut property ### The problem Anticipating Lecture 12: a **spanning tree** of a connected graph $G$ is a subgraph that is a tree (connected, acyclic) and includes *every* vertex; it necessarily has exactly $n-1$ edges. A **minimum spanning tree (MST)** is a spanning tree of *least total edge weight*. MSTs answer "what is the cheapest set of links that keeps the whole network connected?" — laying cable, roads, or pipelines; they also seed clustering algorithms and give a $2$-approximation for the metric traveling-salesman problem. Both algorithms that follow are greedy, and both are proved correct by a single lemma. To state it we need the vocabulary of *cuts*. **Cut.** A **cut** $(S,\ V\setminus S)$ is a partition of the vertices into two nonempty parts. **Crossing edge.** An edge **crosses** the cut if it has one endpoint in $S$ and the other in $V\setminus S$. **Light edge.** A crossing edge of minimum weight is a **light edge** of the cut. **Respecting a cut.** A set of edges $A$ **respects** the cut if *no* edge of $A$ crosses it. **Safe edge.** An edge $e$ is **safe** for $A$ if $A\subseteq$ (some MST) implies $A\cup\{e\}\subseteq$ (some MST). ### The cut property **Theorem 11.6 (Cut Property).** Let $A$ be a set of edges contained in some MST of $G$. Let $(S,V\setminus S)$ be any cut that $A$ respects, and let $e$ be a light edge crossing this cut. Then $e$ is **safe** for $A$. *Proof (exchange argument).* Let $T$ be an MST with $A\subseteq T$. If $e\in T$ we are done, since then $A\cup\{e\}\subseteq T$. So suppose $e=(u,v)\notin T$, with $u\in S$ and $v\in V\setminus S$. Adding $e$ to the tree $T$ creates exactly **one** cycle $\mathcal C$ (a fundamental fact about trees, Lecture 12: any two vertices already have a unique path in $T$, and $e$ closes it into a cycle). Traversing $\mathcal C$, we start at $u\in S$, use $e$ to reach $v\in V\setminus S$, and eventually return to $u$; since each crossing switches sides and we must end where we began, $\mathcal C$ crosses the cut an **even** number of times. It crosses once at $e$, so it crosses at least once **more**, at some edge $e'\ne e$. This $e'$ is not in $A$: it crosses the cut, but $A$ respects the cut (no $A$-edge crosses). Now exchange: set $T' = (T\setminus\{e'\})\cup\{e\}$. Removing $e'$, an edge on the cycle $\mathcal C$, keeps $T'$ connected; it still has $n-1$ edges, so $T'$ is a spanning tree. Its weight is $$ w(T') = w(T) - w(e') + w(e). $$ Because $e$ is a light (minimum-weight) crossing edge and $e'$ also crosses, $w(e)\le w(e')$, so $w(T')\le w(T)$. But $T$ is an MST, so $w(T')\ge w(T)$; hence $w(T')=w(T)$ and $T'$ is *also* an MST. Finally $A\subseteq T'$ (we removed $e'\notin A$ and added $e$) and $e\in T'$, so $A\cup\{e\}\subseteq T'$: the edge $e$ is safe. $\square$ **Theorem 11.7 (Cycle Property).** For any cycle $\mathcal C$ in $G$, if $e$ is a strict-maximum-weight edge of $\mathcal C$, then $e$ belongs to **no** MST. *Proof.* If some MST $T$ contained $e$, deleting $e$ splits $T$ into two components; the rest of the cycle $\mathcal C\setminus\{e\}$ is a path joining $e$'s endpoints, so it contains some edge $e'$ crossing that split with $w(e')6$, so $\text{key}[F]$ is unchanged. - **Step 6** — extract $F$ (key $6$), add $D\text{–}F$. Tree complete. MST edges: $\{A\text{–}C,\ B\text{–}C,\ B\text{–}D,\ D\text{–}E,\ D\text{–}F\}$; total weight $2+1+5+3+6 = \mathbf{17}$. Five edges for six vertices — a valid spanning tree. Notice Prim added the weights in the order $2,1,5,3,6$: it takes the cheapest *frontier* edge, which is generally **not** the globally cheapest remaining edge (contrast Kruskal). ### Correctness **Theorem 11.9.** Prim's algorithm returns a minimum spanning tree. *Proof.* Let $A$ be the set of edges chosen so far, and $S$ the set of vertices in the tree (those with $\text{inMST}=\text{true}$). We prove the invariant *$A$ is contained in some MST* by induction on the steps. *Base.* Initially $A=\varnothing\subseteq T$ for any MST $T$. *Step.* Assume $A\subseteq$ some MST. Consider the cut $(S,V\setminus S)$. Every edge of $A$ joins two vertices that entered the tree, hence lies inside $S$, so $A$ **respects** this cut. The next edge Prim adds is, by construction, the minimum-weight edge from $S$ to $V\setminus S$ — a **light edge** of the cut. By the Cut Property (Theorem 11.6) this edge is *safe*, so $A\cup\{e\}$ is contained in some MST. The invariant is maintained. When $Q$ empties, $S=V$ and $A$ has $n-1$ edges forming a spanning tree contained in an MST; a spanning tree contained in an MST *is* that MST. $\square$ (The algorithm never gets stuck while $S\ne V$: because $G$ is connected there is always at least one edge crossing the cut, so some vertex has finite key.) ### Complexity Structurally Prim is Dijkstra with a different key ("cheapest edge into the tree" instead of "distance from source"), so it has the identical cost profile: - **Binary heap:** $O((V+E)\log V) = O(E\log V)$. - **Unsorted array:** $O(V^2)$ — *preferred for dense graphs*, since it is independent of $E$. - **Fibonacci heap:** $O(E + V\log V)$. **Common pitfall.** Prim needs the graph to be **connected**; on a disconnected graph it only spans the start vertex's component (a *minimum spanning forest* requires restarting from each component). Also, only relax to vertices *not yet in the tree* — relaxing to in-tree vertices is wasted work and can corrupt keys if written carelessly. --- ## 11.10 Kruskal's algorithm ### Idea and pseudocode **Kruskal's algorithm** attacks the MST from the *edges*. It sorts **all** edges by increasing weight and scans them, adding an edge to a growing **forest** whenever it does **not** create a cycle — i.e. whenever its endpoints lie in *different* components. It stops after $n-1$ edges have been added. The one nontrivial operation is testing "same component?" quickly, and updating components after a merge. That is exactly the job of a **disjoint-set (union–find)** data structure. ``` function Kruskal(G, w): A ← ∅ # MST edge set for each vertex v: MakeSet(v) sort all edges of G by weight, ascending for each edge (u, v) in sorted order: if Find(u) ≠ Find(v): # endpoints in different components A ← A ∪ { (u, v) } Union(u, v) if |A| = n - 1: break # tree complete return A ``` ### The union–find (disjoint-set) data structure **Union–find** maintains a partition of the vertices into disjoint sets — the components of the forest built so far — supporting three operations: - `MakeSet(x)` — put $x$ in its own singleton set; - `Find(x)` — return a canonical **representative** (root) of $x$'s set; two elements are in the same set **iff** their representatives are equal; - `Union(x, y)` — merge the two sets containing $x$ and $y$. ![Union-find: disjoint sets stored as rooted trees; find follows to root, union links roots](img/l11_unionfind.png) Each set is stored as a rooted tree via a `parent` array (the root points to itself); `Find` walks parent pointers to the root. Two optimizations keep the trees flat: - **Union by rank** — each root carries a `rank` (an upper bound on its tree's height). `Union` hangs the *lower*-rank root under the *higher*-rank root, so the height grows only when two equal-rank trees merge. - **Path compression** — during `Find`, re-point every node on the path directly to the root, so future queries are $O(1)$. ``` function Find(x): if parent[x] ≠ x: parent[x] ← Find(parent[x]) # path compression return parent[x] function Union(x, y): rx ← Find(x); ry ← Find(y) if rx = ry: return if rank[rx] < rank[ry]: swap(rx, ry) # union by rank: attach smaller under larger parent[ry] ← rx if rank[rx] = rank[ry]: rank[rx] ← rank[rx] + 1 ``` **Complexity.** With **both** optimizations, any sequence of $q$ operations on $n$ elements runs in $O\big(q\,\alpha(n)\big)$ time (Tarjan, 1975), where $\alpha$ is the *inverse Ackermann function* — it grows so slowly that $\alpha(n)\le 4$ for every $n$ that could be written down in the physical universe. So each operation is *effectively constant* time, "near-linear" overall. (Either optimization alone gives $O(\log n)$ per operation; together they are strictly better.) **A concrete union–find trace.** Watch the structure through Kruskal's *unions* on $G$ (shown next). Start with every vertex its own root, all ranks $0$. | Operation | Effect (parent / rank changes) | Roots afterward | |:----------|:-------------------------------|:----------------| | `Union(B,C)` | equal ranks: $\text{parent}[C]{=}B$, $\text{rank}[B]{=}1$ | $B\!:\!\{B,C\}$ | | `Union(A,C)` | $\text{Find}(C){=}B$ (rank 1) $>$ $A$ (rank 0): $\text{parent}[A]{=}B$ | $B\!:\!\{A,B,C\}$ | | `Union(D,E)` | equal ranks: $\text{parent}[E]{=}D$, $\text{rank}[D]{=}1$ | $D\!:\!\{D,E\}$ | | `Union(B,D)` | equal ranks $1$: $\text{parent}[D]{=}B$, $\text{rank}[B]{=}2$ | $B\!:\!\{A,B,C,D,E\}$ | | `Union(D,F)` | $\text{Find}(D){=}B$ (rank 2) $>$ $F$ (rank 0): $\text{parent}[F]{=}B$ | $B\!:\!\{A,\dots,F\}$ | After these, a call to `Find(E)` walks $E\to D\to B$ and, by path compression, re-points $\text{parent}[E]\leftarrow B$ so the next `Find(E)` is a single hop — this is path compression in action. ### Worked trace Same graph $G$. Sorted edges: $BC(1), AC(2), DE(3), AB(4), BD(5), DF(6), EF(7), CD(8), CE(10)$. | Edge | $w$ | $\text{Find}(u)$ vs $\text{Find}(v)$ | Cycle? | Action | Components after | |:----:|:---:|:------------------------------------:|:------:|:-------|:-----------------| | $B\text{–}C$ | 1 | $B\ne C$ | no | **add** | $\{BC\},\{A\},\{D\},\{E\},\{F\}$ | | $A\text{–}C$ | 2 | $A\ne C$ | no | **add** | $\{ABC\},\{D\},\{E\},\{F\}$ | | $D\text{–}E$ | 3 | $D\ne E$ | no | **add** | $\{ABC\},\{DE\},\{F\}$ | | $A\text{–}B$ | 4 | $A=B$ | **yes** | skip | $\{ABC\},\{DE\},\{F\}$ | | $B\text{–}D$ | 5 | $B\ne D$ | no | **add** | $\{ABCDE\},\{F\}$ | | $D\text{–}F$ | 6 | $D\ne F$ | no | **add** | $\{ABCDEF\}$ | | $E\text{–}F$ | 7 | — | — | ($n{-}1$ reached) | — | | $C\text{–}D$ | 8 | — | — | — | — | | $C\text{–}E$ | 10 | — | — | — | — | MST edges: $\{B\text{–}C,\ A\text{–}C,\ D\text{–}E,\ B\text{–}D,\ D\text{–}F\}$; total weight $1+2+3+5+6=\mathbf{17}$. **This is exactly the tree Prim found** (both equal $\{AC,BC,BD,DE,DF\}$, weight $17$) — as Corollary 11.8 guarantees, since $G$'s weights are distinct. The edge $A\text{–}B(4)$ was *skipped* because $A$ and $B$ were already in the same component $\{ABC\}$: adding it would close the cycle $A\text{–}C\text{–}B\text{–}A$, on which $A\text{–}B$ is the heaviest edge. ### Correctness **Theorem 11.10.** Kruskal's algorithm returns a minimum spanning tree. *Proof.* Again we show the invariant *the chosen set $A$ is contained in some MST*, by induction on additions. The base case $A=\varnothing$ is immediate. Suppose $A\subseteq$ some MST and Kruskal is about to **add** edge $e=(u,v)$ because $\text{Find}(u)\ne\text{Find}(v)$. Let $S$ be the component of $u$ in the current forest $A$, and take the cut $(S,V\setminus S)$. Every edge of $A$ lies within a single component, so no $A$-edge crosses this cut: $A$ **respects** it. Moreover $e$ crosses it (its endpoints are in different components, one being $S$). *Claim: $e$ is a light edge of this cut.* Suppose some crossing edge $e'$ had $w(e')2,1$). **7.** Both give $\{A\text{–}C,B\text{–}C,B\text{–}D,D\text{–}E,D\text{–}F\}$, weight $17$. The sets are **identical** because all nine weights are distinct, so the MST is unique (Corollary 11.8). **11.** $E$ was first set to $12$ when $C$ was finalized (edge $C\text{–}E$, $2+10$); it improved to $11$ when $D$ was finalized and edge $D\text{–}E$ gave $8+3=11<12$. Later, from $E$, edge $E\text{–}F$ offers $11+7=18$, which is $>\text{dist}[F]=14$ (set via $D\text{–}F$), so no update. **12.** Directed $A\to B(2),\ A\to C(3),\ C\to B(-2)$. Dijkstra finalizes $B$ at $2$ (it is the current minimum) before examining $C$, so it reports $\text{dist}[B]=2$; but $A\to C\to B$ costs $3-2=1$, the true distance. Use **Bellman–Ford** for negative weights. **14.** Processing unions $B{\cup}C,\ A{\cup}C,\ D{\cup}E,\ B{\cup}D,\ D{\cup}F$ yields root $B$ with $\text{rank}[B]=2$; $\text{parent}$: $A\to B,\ C\to B,\ D\to B,\ E\to D,\ F\to B$. `Find(E)` walks $E\to D\to B$, returns $B$, and by path compression sets $\text{parent}[E]\leftarrow B$ (so a subsequent `Find(E)` is one hop). **15.** Lowering $E\text{–}F$ to $0$ makes it the cheapest edge; the new MST is $\{A\text{–}C,B\text{–}C,B\text{–}D,D\text{–}E,E\text{–}F\}$ of weight $11$. The edge $D\text{–}F(6)$ **leaves**: in Kruskal, $E\text{–}F$ now precedes it and already connects $F$; equivalently, on the cycle $D\text{–}E\text{–}F\text{–}D$ the heaviest edge is now $D\text{–}F$, which the cycle property excludes. **18.** If two distinct MSTs $T_1\ne T_2$ existed, take the minimum-weight edge $e$ in their symmetric difference, say $e\in T_1$. Adding $e$ to $T_2$ makes a cycle; by distinctness some cycle edge $e'\in T_2\setminus T_1$ has $w(e')>w(e)$ (else $e$ would not be minimal in the difference), and swapping $e$ for $e'$ gives a lighter spanning tree than $T_2$ — contradiction. Hence the MST is unique. **19.** By induction: $x_0$ gets $1$; $y_0$ (non-adjacent to $x_0$) gets $1$; and when we reach $x_k,y_k$ their already-colored neighbors are exactly $\{x_i,y_i : i