In the 1730s the Prussian city of Königsberg (now Kaliningrad, Russia) sat on both banks of the river Pregel and on an island, Kneiphof, with a fourth piece of land to the east where the river forked. Seven bridges joined the four land masses. The townspeople asked: can you take a walk that crosses every bridge exactly once? Nobody could find one, and nobody could prove it impossible.

In 1736 Leonhard Euler saw that almost nothing on the map matters. The size and shape of the land, the lengths of the bridges, the route you take while on dry land: all irrelevant. Only two things matter: which land masses exist and which pairs each bridge connects. So shrink each land mass to a dot and draw each bridge as a line between dots:

Now think about any walk that crosses each bridge once. Every time the walk passes through a land mass, it arrives on one bridge and leaves on another, using up bridges in pairs. So every land mass that is not the start or the end of the walk must touch an even number of bridges. At most two land masses (the start and the end) can have an odd number. In Königsberg, all four have an odd number (5, 3, 3, 3). So no such walk exists. No amount of trying would ever have found one. Try it: Königsberg as a graph.

That argument is the birth of graph theory, and it illustrates the subject’s power: by finding the right abstraction, a question about a city becomes a question about counting, and the answer comes with a proof. We will make it precise in Section 25.7.

A graph is the simplest possible model of "things and connections": a set of objects, and a set of pairs of objects that are linked.

Modelling is the first skill. Ask: what are the things (vertices), and what is the relationship (edges)? Is the relationship symmetric (undirected) or not (directed)? Does it have a size (weighted)?

A directed edge is a pair, which is exactly a relation in the sense of Chapter 21. A directed graph is a relation on \(V\), drawn as a picture; an undirected graph is a symmetric relation.

At a meeting, people shake hands; you ask everyone how many hands they shook and add up the answers. Can the total be odd?

Proof (double counting). Count the pairs (vertex, edge) where the edge is incident to the vertex. Counting vertex by vertex, each vertex \(v\) contributes \(\deg(v)\) pairs, for a total of \(\sum \deg(v)\). Counting edge by edge, each edge has exactly two endpoints and contributes exactly 2 pairs, for a total of \(2|E|\). Both count the same set, so they are equal. \(\blacksquare\)

In Königsberg: \(3 + 5 + 3 + 3 = 14 = 2 \times 7\). ✓

Corollary: the number of odd-degree vertices is even. Split the sum into even-degree and odd-degree vertices. The total \(2|E|\) is even and the even-degree part is even, so the odd-degree part is even. A sum of odd numbers is even only if there is an even number of them. So the answer to the handshake question is no: the total is always even, and the number of people who shook an odd number of hands is always even.

For a directed graph the analogue is \(\sum \deg^{+}(v) = \sum \deg^{-}(v) = |E|\): every arrow leaves exactly one vertex and arrives at exactly one.

Is there a simple graph with degrees \(3, 3, 3, 3, 3\)? The sum is 15, which is odd, but it must equal \(2|E|\). No.

Is there a simple graph with degrees \(4, 4, 4, 1, 1\)? The sum is 14, so it would have 7 edges, and the parity test passes. But look harder: three vertices of degree 4 in a 5-vertex simple graph must each be adjacent to every other vertex, including both degree-1 vertices. Then each degree-1 vertex would have at least 3 neighbours. Contradiction. No. The parity test is necessary, not sufficient.

Movement through a graph has several flavours, and the words are used carefully.

A useful fact: every walk from \(u\) to \(v\) contains a path from \(u\) to \(v\). If a walk revisits a vertex, cut out the loop between the two visits; repeat until no vertex repeats. So "reachable by a walk" and "reachable by a path" mean the same thing, and the shortest walk is always a path.

You need to connect \(n\) offices with network cable so that every office can reach every other. What is the smallest number of links that can do it, and what do minimal networks look like?

Start with \(n\) isolated offices: \(n\) components. Each new link can merge at most two components into one, reducing the count by at most 1. To get down to a single component you need at least \(n - 1\) links. And a network that uses exactly \(n - 1\) has no spare links: every link is essential, so there are no cycles (a link in a cycle could be removed without disconnecting anything). Such minimal connected graphs are trees.

Lemma. Every tree with \(n \ge 2\) vertices has at least two leaves.

Proof. Take a longest path \(v_0, v_1, \ldots, v_k\) in the tree. Suppose \(v_0\) had a neighbour other than \(v_1\). If that neighbour were on the path, it would close a cycle; if it were off the path, it would extend the path, contradicting "longest". So \(\deg(v_0) = 1\), and by symmetry \(\deg(v_k) = 1\). \(\blacksquare\)

Theorem. A tree with \(n\) vertices has exactly \(n - 1\) edges.

Proof by induction on \(n\) (Chapter 22). For \(n = 1\), a single vertex has 0 edges. ✓ Suppose every tree with \(n - 1\) vertices has \(n - 2\) edges, and let \(T\) have \(n \ge 2\) vertices. By the lemma, \(T\) has a leaf \(\ell\). Removing \(\ell\) and its one edge leaves a graph that is still connected (no path between other vertices passed through a leaf) and still acyclic: a tree with \(n - 1\) vertices, hence \(n - 2\) edges. Putting \(\ell\) back adds one edge: \(n - 1\). \(\blacksquare\)

The following are all equivalent for a graph with \(n\) vertices; any two of the first three imply the third:

Property 4 is why trees are the natural shape for hierarchies: file systems, the DOM, organisational charts, parse trees, and the "parent pointer" structures that BFS and DFS produce.

Chemistry: alkanes are trees. Draw a molecule with atoms as vertices and bonds as edges. An alkane \(\mathrm{C}_n\mathrm{H}_{2n+2}\) has \(3n + 2\) atoms, and its degree sum is \(4n\) (carbon) \(+ (2n + 2)\) (hydrogen) \(= 6n + 2\), so by the handshake lemma it has \(3n + 1\) bonds: exactly one fewer than its atoms. A connected graph with that many edges is a tree, so alkanes have no rings. The different isomers are the different trees the carbons can form: butane (\(n = 4\)) has 2 (a chain and a branched one), pentane has 3. Cayley’s interest in counting trees came from exactly this question.

Engineering: radial networks. Local electricity distribution networks are usually operated as trees, even when extra cables exist: with \(n\) substations and exactly \(n - 1\) closed links, there is one path from the supply to each customer, so a fault is easy to locate and isolate. Close one more link and you create a loop, which is what engineers do deliberately (and briefly) to reroute power during repairs.

Everyday and science. Family trees (going back one generation per level), company org charts, folder hierarchies and the "tree of life" in evolutionary biology are all rooted trees; a phylogenetic tree of \(n\) species, with branching ancestors as extra vertices, is built by the same "no cycles, everything connected" logic.

Four developers and four services: each developer can maintain certain services. Can every service get a distinct maintainer? Problems like this pair up things of two different kinds, and edges only ever run between the kinds.

Try it: Two-colour the developer graph.

Theorem. A graph is bipartite if and only if it has no cycle of odd length. Try it: Watch two-colouring find odd cycles.

Why: walking round a cycle in a bipartite graph alternates sides, L, R, L, R, …, and you can only return to your starting side after an even number of steps. Conversely, if there are no odd cycles, colour a start vertex 0, its neighbours 1, their neighbours 0, and so on outward (breadth-first); a clash would mean two vertices at the same parity of distance are adjacent, which closes an odd cycle.

That proof is an algorithm. Here it is, using breadth-first search from Section 25.10:

In the developer graph above, a perfect matching exists (Ana–billing, Ben–search, Chi–web, Dev–auth, for instance). Finding maximum matchings efficiently is a classic algorithmic problem (Hopcroft–Karp, network flow) behind job assignment, ad allocation, organ-donor exchanges and medical residency placement.

The residency match is the famous large-scale example. Each year the US National Resident Matching Program pairs tens of thousands of newly qualified doctors with hospital training posts. The algorithm behind it finds a stable matching in a bipartite graph (no doctor and hospital would both prefer each other to what they got). Its theory, by David Gale and Lloyd Shapley, and its practice, by Alvin Roth, won the 2012 Nobel prize in economics. School-place allocation in cities such as New York and Boston uses the same algorithm. Closer to home, assigning 4 people to 4 chores they are each willing to do is a perfect-matching question, and the developer example above is the workplace version.

Return to Königsberg, generalised. Given a connected graph, can you traverse every edge exactly once? A snowplough wants to clear every street once; a pen-plotter wants to draw a figure without lifting the pen; a DNA-sequencing algorithm wants to chain overlapping fragments.

Theorem (Euler 1736, Hierholzer 1873). Let \(G\) be a connected graph (ignoring isolated vertices).

Necessity is the Königsberg argument. Each time a trail passes through a vertex, it uses one edge in and one edge out: a pair. For a circuit, the start vertex is also paired (the first edge out with the last edge in), so every degree is even. For an open path, only the two endpoints have an unpaired edge, so exactly those two have odd degree.

Sufficiency (that the condition is enough) is constructive. Start anywhere and keep walking along unused edges. With all degrees even, whenever you enter a vertex other than the start, an unused edge remains to leave by, so you can only get stuck back at the start: you have a closed trail. If it hasn’t used every edge, some vertex on it still has unused edges (the graph is connected); start a new closed trail there, using only unused edges, and splice it into the first. Repeat until every edge is used. This is Hierholzer’s algorithm, which runs in \(O(|E|)\) time. For the two-odd-vertex case, add an imaginary edge between the odd vertices, find a circuit, then delete the imaginary edge.

The "house" or "open envelope" puzzle asks you to draw this figure without lifting your pen or retracing a line. Try it: Trace the house’s Euler path.

Degrees: \(P = 2\), \(Q = 4\), \(R = 4\), \(S = 3\), \(T = 3\). Sum \(16 = 2 \times 8\). ✓ Two odd vertices, so an Euler path exists and must start at S or T. One such path:

Check: 8 steps, using the edges ST, TR, RS, SQ, QR, RP, PQ, QT, which are all 8 edges, each once. Start at P instead and you will always get stuck, which is now a theorem rather than a frustration.

Try it: Even degrees, two components.

Route planning for every street. Gritting lorries, street sweepers, postal rounds and meter readers want a closed route that covers every street, and every repeated street costs fuel. If every junction has even degree, an Euler circuit does it with no repeats. Otherwise the odd-degree junctions must be paired up and a shortest path between each pair driven twice: the Chinese postman problem, first posed by the Chinese mathematician Meigu Guan in 1960. In the house above, a sweeper that must return to its depot has to repeat one street: the S–T edge, giving 9 street-traversals for 8 streets.

Drawing machines. A pen plotter, laser cutter or CNC router drawing a connected outline wastes time on "pen-up" moves. An outline whose graph has \(2k\) odd vertices needs at least \(k\) separate strokes, so a figure with all even degrees can be cut in one continuous pass.

Change one word. Instead of using every edge once, visit every vertex once. A delivery van must call at every depot; a tour must visit every city.

The two questions look like twins, but they behave completely differently.

Why is the vertex version so much harder? The Euler condition is local: each vertex just needs the right parity, and the pieces can always be spliced together. Whether a vertex can be fitted into a Hamiltonian cycle depends on the global structure of the whole graph. The obvious algorithm is to try every ordering of the vertices, and there are \((n-1)!/2\) distinct cycles on \(n\) labelled vertices of a complete graph (Chapter 24). For 20 cities that is about \(6 \times 10^{16}\). Try it: Brute-force Hamiltonian cycles (cube).

There are useful sufficient conditions. Dirac’s theorem (1952): if a simple graph has \(n \ge 3\) vertices and every vertex has degree at least \(n/2\), then it has a Hamiltonian cycle. But many graphs with low degrees are Hamiltonian too (any cycle graph, for instance), so the condition is far from necessary.

For small graphs (up to about 20 vertices), exact dynamic programming over subsets (the Held–Karp algorithm, \(O(n^2 2^n)\)) is practical. For larger TSP instances, practitioners use heuristics (nearest neighbour, 2-opt improvement) and branch-and-bound solvers, which routinely solve real instances with tens of thousands of cities to optimality or near it, even though no guarantee of speed exists. "NP-hard" means "no known algorithm is fast on every input", not "hopeless in practice". Try it: Brute force vs nearest neighbour.

To run algorithms you need a data structure. The two standard choices make different operations fast, and the right choice depends on how dense the graph is.

Number the vertices \(0, \ldots, n-1\). The adjacency matrix \(A\) is the \(n \times n\) table with \(A_{ij} = 1\) if there is an edge from \(i\) to \(j\) and \(0\) otherwise (or the edge weight, for a weighted graph). For an undirected graph \(A\) is symmetric: \(A_{ij} = A_{ji}\).

For the directed graph with edges \(0 \to 1\), \(0 \to 2\), \(1 \to 2\), \(2 \to 0\), \(2 \to 3\), \(3 \to 0\):

The adjacency list stores, for each vertex, a list of its neighbours. In Python this is naturally a dictionary of lists:

Choosing. Most real graphs are sparse: \(m\) is much smaller than the maximum \(\binom{n}{2}\). A social network with a billion users and a few hundred friends each has around \(10^{11}\) edges, while its adjacency matrix would have \(10^{18}\) cells, nearly all zero. Use adjacency lists by default. Use a matrix when the graph is small or dense (most pairs connected), when you need constant-time edge queries, or when you want to apply linear algebra. In numerical work, sparse matrix formats give you the memory of a list with the algebra of a matrix.

Here is a first taste of how matrices and graphs reinforce each other. Matrix multiplication is defined in Chapter 27; for now you need only the rule for one entry: \((A^2)_{ij} = \sum_{k} A_{ik} A_{kj}\). Try it: Count walks with powers of A.

Each term \(A_{ik}A_{kj}\) is 1 exactly when there is an edge \(i \to k\) and an edge \(k \to j\), that is, a walk \(i \to k \to j\) of length 2. The sum over all intermediate vertices \(k\) therefore counts the walks of length 2 from \(i\) to \(j\). By induction, \((A^r)_{ij}\) is the number of walks of length \(r\) from \(i\) to \(j\).

Check by hand. \((A^2)_{03} = 1\): the only length-2 walk from 0 to 3 is \(0 \to 2 \to 3\). \((A^3)_{00} = 2\): the two closed walks of length 3 from 0 are \(0 \to 1 \to 2 \to 0\) and \(0 \to 2 \to 3 \to 0\). The diagonal of \(A^3\) counts closed 3-walks through each vertex; in an undirected graph each triangle through a vertex gives two of them (one per direction), so the total number of triangles is \(\operatorname{trace}(A^3)/6\), a formula used in network analysis. Try it: Closed 3-walks versus triangles.

Given a graph and a start vertex, which vertices can you reach, and what is the fewest number of edges needed to reach each one? This is "degrees of separation", "minimum number of hops", "fewest moves to solve the puzzle".

Explore in rings. First the start vertex (distance 0). Then all its neighbours (distance 1). Then all their unvisited neighbours (distance 2). And so on. A queue (first in, first out) enforces this order automatically: vertices discovered earlier are processed earlier, so you finish each ring before starting the next.

Adjacency lists (neighbours in alphabetical order): A: B, C; B: A, D; C: A, D, E; D: B, C, F; E: C, F, G; F: D, E, H; G: E; H: F. Try it: Step BFS and DFS.

Visit order: A, B, C, D, E, F, G, H. Distances: \(A{:}0\), \(B, C{:}1\), \(D, E{:}2\), \(F, G{:}3\), \(H{:}4\). A shortest path to H, read from the parent pointers backwards: \(H \leftarrow F \leftarrow D \leftarrow B \leftarrow A\), i.e. \(A, B, D, F, H\).

The queue always holds vertices of at most two consecutive distances, \(d\) then \(d + 1\), in that order. So every distance-\(d\) vertex is removed before any distance-\((d+1)\) vertex, and the first time a vertex is discovered, it is discovered from a vertex as close to \(s\) as possible. Each vertex enters the queue once and each adjacency list is scanned once, so BFS takes \(O(n + m)\) time: linear in the size of the graph.

Depth-first search is how you explore a maze with a ball of string: always go deeper down an unexplored passage; when you reach a dead end, back up to the most recent junction with an unexplored passage, and try that. Replace BFS’s queue with a stack, or use recursion (which keeps a stack for you), and you have DFS.

On the same graph, from A: Try it: DFS trace, step by step.

Discovery order: A, B, D, C, E, F, H, G. Compare BFS (A, B, C, D, E, F, G, H): DFS plunged to H before ever touching G, a neighbour of E.

DFS also runs in \(O(n + m)\) time.

Edges now have lengths: road distances, network latencies, costs. Find the cheapest route from a source \(S\) to every other vertex. BFS no longer works: the path with fewest edges need not be the cheapest.

Imagine pouring water in at \(S\), flowing along edges at constant speed. The water reaches vertices in order of their true distance. Dijkstra’s algorithm simulates this. It keeps a tentative distance for each vertex: the length of the best route found so far. At each step it takes the unfinished vertex with the smallest tentative distance and declares that distance final. Then it checks whether going through this newly finished vertex gives a shorter route to any of its neighbours, an update called relaxing an edge.

Suppose \(u\) is the unfinished vertex with smallest tentative distance \(d\). Any other route to \(u\) must leave the finished region somewhere, through some unfinished vertex \(x\) with tentative distance at least \(d\), and then continue along edges of non-negative weight. So it costs at least \(d\). Hence \(d\) is the true distance, and finalising \(u\) is safe. This is a greedy algorithm (it makes the locally best choice and never revisits it) whose correctness rests entirely on weights being non-negative.

Edges (undirected): SA 4, SB 2, AB 1, AC 5, BC 8, BD 10, CD 2, CT 6, DT 2. Each cell shows the tentative distance and, in brackets, the parent. A bold entry is finalised in that step; a dash means the vertex was already finished. Try it: Step through this trace.

Step by step:

Read the path backwards from T using parents: \(T \leftarrow D \leftarrow C \leftarrow A \leftarrow B \leftarrow S\). The shortest route is \(S \to B \to A \to C \to D \to T\) with length \(2 + 1 + 5 + 2 + 2 = 12\). Notice that the direct-looking edge SA (4) is not on any shortest path, and that the fewest-edge route S–B–D–T (length \(2 + 10 + 2 = 14\)) loses.

The priority queue (heapq, a binary heap) finds the smallest tentative distance in \(O(\log n)\) time instead of scanning every vertex. Rather than updating entries inside the heap, the code pushes a new entry on every improvement and skips "stale" entries when they surface. The total running time is \(O((n + m)\log n)\).

Take vertices S, A, B with edges \(S \to A\) (weight 2), \(S \to B\) (weight 3) and \(B \to A\) (weight \(-2\)). Dijkstra finishes A first at distance 2, because it is the nearest unfinished vertex, and never reconsiders it. But \(S \to B \to A\) costs \(3 - 2 = 1\). The greedy argument broke because a later edge could reduce a total. Try it: Watch the negative edge fool Dijkstra.

Navigation. A phone’s route planner runs a refined Dijkstra (A* search plus precomputed shortcuts called contraction hierarchies) on road graphs with tens of millions of junctions. The weights are travel times, not distances, which is why "fastest" and "shortest" routes differ. Public-transport journey planners do the same on a graph whose vertices are (stop, time) pairs.

Finance: spotting arbitrage. Exchange rates multiply along a path, but shortest-path algorithms add. Taking logarithms fixes that: give the edge from currency \(X\) to \(Y\) the weight \(-\ln(\text{rate})\). Suppose USD \(\to\) EUR is 0.90, EUR \(\to\) GBP is 0.90 and GBP \(\to\) USD is 1.25. Round the cycle, $1 becomes \(0.90 \times 0.90 \times 1.25 = 1.0125\) dollars, and the weights sum to \(-\ln 1.0125 < 0\): a negative cycle. Bellman–Ford (the table above) detects negative cycles, which is why it, not Dijkstra, is the textbook tool for this. (Real markets close such gaps within milliseconds.) Try it: Find the arbitrage cycle.

Networks. Internet routers inside one organisation run OSPF, which is Dijkstra on the link-state graph, recomputed whenever a link fails.

Some tasks must happen before others. A course has prerequisites; a source file must be compiled before the program that links it; a package must be installed before the packages that depend on it. Given all the "must come before" constraints, find an order that respects every one of them.

This book is itself an example. The map at the front (The Knowledge Map) is a directed graph whose edges say "read this chapter first". Here is a fragment:

Theorem. A directed graph has a topological order if and only if it is a DAG.

If there is a cycle \(v_1 \to v_2 \to \cdots \to v_k \to v_1\), then \(v_1\) must come before itself, which is impossible. Conversely, every DAG has a source (follow edges backwards from any vertex; with no cycles and finitely many vertices you must reach a vertex with no incoming edge). Put a source first, delete it, and the rest is still a DAG; repeat. That argument is Kahn’s algorithm.

In-degrees at the start: numbers 0, logic 0, powers 1, expressions 2, linear 1, functions 1, proof 1, combinatorics 2, graphs 1, probability 2. When several vertices are ready, take them alphabetically (any choice gives a valid order). Try it: Step through Kahn’s algorithm.

Order: logic, numbers, powers, expressions, linear, functions, proof, combinatorics, graphs, probability. Every arrow points forward.

Try it: Add the cycle, watch it stall.

Alternative method. Run DFS and list vertices in order of finishing time, then reverse the list. A vertex finishes only after everything reachable from it has finished, so in the reversed list it comes before all of its descendants. Both methods are \(O(n + m)\). Kahn’s algorithm is easier to explain, naturally reports cycles, and shows which tasks can run in parallel (everything in ready at the same moment); the DFS method is shorter to code when you already have DFS.

Project planning: the critical path. A small building job has five tasks: foundation (3 weeks), then walls (4 weeks) and plumbing (2 weeks), roof after the walls (2 weeks), and finishing after both roof and plumbing (1 week). Any topological order is a valid schedule. The shortest possible project length is the longest path through the DAG: foundation \(\to\) walls \(\to\) roof \(\to\) finishing, \(3 + 4 + 2 + 1 = 10\) weeks. Plumbing lies on a path of only \(3 + 2 + 1 = 6\) weeks, so it has 4 weeks of slack; a delay on the critical path delays the whole job. Engineers call this the critical path method, and it was developed in the late 1950s to schedule large construction and defence projects. Try it: Find the critical path.

Everyday. A recipe is a DAG: you cannot sauté onions you have not chopped, but you can boil the water while you chop. Reading the steps as a dependency graph tells you what can happen in parallel and which step sets the time the meal is ready.

You must connect six sites with fibre. Each possible link has a cost. Every site must be able to reach every other (possibly indirectly), and you want the cheapest network. By Section 25.5, a cheapest such network has no cycles (removing a cycle edge saves money and keeps everything connected), so it is a spanning tree: a minimum spanning tree (MST).

Sort the edges from cheapest to dearest. Take each edge in turn, and keep it unless it would form a cycle with the edges already kept. Stop when you have \(n - 1\) edges.

Worked trace (edges: BC 1, BD 2, AC 3, EF 3, AB 4, CD 4, CE 5, DF 6, DE 7): Try it: Step through Kruskal.

Total weight \(1 + 2 + 3 + 3 + 5 = 14\).

The "same component?" test uses a union–find (disjoint-set) structure, which answers it in nearly constant time; sorting dominates, so Kruskal runs in \(O(m \log m)\).

Why greedy works here (the cut property). Split the vertices into any two groups. The cheapest edge crossing between the groups belongs to some MST: if a spanning tree avoided it, adding it would create a cycle that crosses the split at least twice, and swapping out the other, dearer crossing edge would give a tree that is no more expensive. Every edge Kruskal keeps is the cheapest edge crossing between its own component and the rest, so every choice is safe.

Prim’s algorithm grows a single tree from a start vertex: repeatedly add the cheapest edge joining the tree to a vertex not yet in it. It is Dijkstra’s algorithm with one change (the priority of a vertex is the weight of the single edge connecting it, not the total path length) and runs in \(O((n + m)\log n)\) with a heap. Choosing: Kruskal is simple and natural when edges arrive as a list; Prim suits dense graphs and adjacency structures. Both give a minimum total weight; if several edges have equal weights, different MSTs of the same total can result. Try it: Grow the tree with Prim.

Infrastructure. The first MST algorithm was published in 1926 by Otakar Borůvka for a practical problem: designing an economical electricity network for southern Moravia. Treat the example graph above as possible cable routes between six villages with lengths in kilometres. Laying every route would cost \(4 + 3 + 1 + 2 + 4 + 5 + 7 + 6 + 3 = 35\) km of cable; the MST connects all six villages with 14 km. Pipelines, fibre networks and irrigation channels are planned the same way, usually as a starting point before adding a few redundant links for resilience.

Science and data. Biologists and data scientists build an MST on the pairwise distances between samples and then delete its longest edges; the pieces that remain are clusters (single-linkage clustering). The same trick groups similar images, documents or customer records.

Algorithms. For the travelling salesman problem (Section 25.8) with ordinary distances, walking around an MST and skipping repeated cities gives a tour at most twice the optimal length, a quick guaranteed-quality answer to an intractable problem.

Six exams must be scheduled. Two exams that share a student cannot be in the same time slot. What is the smallest number of slots?

Build a conflict graph: one vertex per exam, an edge when two exams share a student. A schedule is an assignment of slots to vertices with adjacent vertices in different slots. Call the slots colours, and this is graph colouring.

Go through the vertices in some order and give each the smallest colour not already used by a coloured neighbour. Try it: Greedy-colour the exams.

Trace for the exams: Algebra gets 0. Biology is adjacent to Algebra (0), so gets 1. Chemistry is adjacent to Algebra (0) and Biology (1), so gets 2. Drama is adjacent to Algebra (0): gets 1. English is adjacent to Biology (1) and Drama (1): gets 0. French is adjacent to Chemistry (2) and English (0): gets 1. Three slots, and the Algebra–Biology–Chemistry triangle proves three is optimal.

The second test colours a crown graph (each \(a_i\) joined to every \(b_j\) with \(j \ne i\)). It is bipartite, so 2 colours suffice, and greedy finds 2 when it colours all the \(a\)'s first. But in the interleaved order \(a_1, b_1, a_2, b_2, \ldots\), greedy uses 4; with \(k\) pairs it would use \(k\). Finding \(\chi(G)\) exactly is NP-hard (even deciding whether 3 colours suffice), so practical systems use good heuristic orders (largest degree first, or DSatur, which colours the most-constrained vertex next) and accept near-optimal answers. Try it: Greedy in a bad order.

Three houses must each be connected to three utilities (water, gas, electricity) by pipes that do not cross. Can it be done on flat ground? Circuit designers ask the same question: can this circuit be laid out on a single layer without wires crossing?

For any connected plane graph with \(V\) vertices, \(E\) edges and \(F\) faces,

Proof by induction on the number of edges. If the graph is a tree, it has no cycles, so there is only the outer face: \(F = 1\), and \(E = V - 1\) (Section 25.5), giving \(V - (V - 1) + 1 = 2\). ✓ If it is not a tree, it has a cycle. Remove one edge of that cycle. The graph stays connected (the rest of the cycle still joins the two endpoints), and the two faces on either side of that edge merge into one. So \(E\) and \(F\) each drop by 1, and \(V - E + F\) is unchanged. Repeat until a tree remains, where the value is 2. \(\blacksquare\)

The cube itself (as a solid) has 8 corners, 12 edges and 6 faces, and \(8 - 12 + 6 = 2\): this is Euler’s polyhedron formula, of which the graph version is a flattened form. Every convex polyhedron obeys it.

In a simple planar graph with \(V \ge 3\), every face is bounded by at least 3 edges, and every edge borders at most 2 faces. Counting (edge, face) border pairs both ways gives \(3F \le 2E\). Substitute \(F = 2 - V + E\) from Euler’s formula:

\(K_5\) is not planar. It has \(V = 5\) and \(E = \binom{5}{2} = 10\), but \(3V - 6 = 9 < 10\). Try it: Test K5 for planarity.

\(K_{3,3}\) (three houses, three utilities) is not planar. It is bipartite, so it has no triangles, and every face has at least 4 edges. The same counting gives \(4F \le 2E\), hence \(E \le 2V - 4 = 2 \times 6 - 4 = 8\). But \(K_{3,3}\) has \(3 \times 3 = 9\) edges. The puzzle is impossible. Try it: Test K3,3 for planarity.

These two graphs are, in a precise sense, the only obstacles. Kuratowski’s theorem (1930): a graph is planar if and only if it does not contain a subdivision of \(K_5\) or \(K_{3,3}\). Linear-time planarity-testing algorithms exist (Hopcroft and Tarjan, 1974).