8. Graph Theory

A graph records which things are connected to which, and nothing else. That abstraction covers road maps, computer networks, social networks, dependency trees, state machines and molecules. This chapter defines graphs and their representations, studies connectivity, traversal and shortest paths, and then turns to the classic structural questions of planarity, coloring, matchings and network flows. Most of these results come with an efficient algorithm that is used in everyday software.

8.1 Graph Fundamentals

This subchapter sets up the vocabulary used in the rest of the chapter: vertices and edges, directed and undirected graphs, degrees, the standard families of graphs, and the ways of building new graphs from old ones.

Graph Terminology

Why. Many problems have the same shape. "Can I drive from Milan to Naples?", "Does this package depend on that one?" and "Are these two people connected through friends?" all ask about objects and the connections between them. A graph keeps only that information and drops distances on the map, the contents of a package and everything else. The payoff is that one algorithm, such as breadth-first search (8.4), answers all three questions.

What. A graph G = (V, E) consists of

a non-empty set V of vertices (also called nodes), and
a set E of edges, where each edge e = {u, v} connects two vertices.

In this chapter, V is finite, n = |V| is the order of the graph, and m = |E| is its size.

Term	Meaning
Endpoints	`u` and `v` are the endpoints of the edge `{u, v}`
Adjacent (neighbors)	`u` and `v` are adjacent if `{u, v} ∈ E`
Incident	An edge is incident to each of its endpoints
Neighborhood `N(v)`	The set of all neighbors of `v`
Loop	An edge from a vertex to itself
Multiple (parallel) edges	Two or more edges with the same endpoints
Isolated vertex	A vertex with no neighbors
Weighted graph	A graph with a number `w(e)` (cost, length, capacity) on each edge

Graphs come in several flavors, depending on which of these features are allowed:

Type	Edges	Multiple edges?	Loops?
Simple graph	Undirected	No	No
Multigraph	Undirected	Yes	No
Pseudograph	Undirected	Yes	Yes
Simple directed graph	Directed	No	Yes
Directed multigraph	Directed	Yes	Yes

Unless stated otherwise, "graph" means a simple graph. A simple graph has at most one edge per pair of distinct vertices, so

  0 ≤ m ≤ C(n, 2) = n(n − 1)/2

Graphs with m close to n²/2 are dense. Graphs with m close to n are sparse. Most real-world graphs are sparse: a social network may have a billion users, but each user has hundreds of friends, not hundreds of millions.

Analogy. A graph is a subway map. Stations are vertices and the track segments between consecutive stations are edges. The map is deliberately distorted: real distances and the shapes of the lines do not matter, only which stations connect to which.

Example.

     a ─────── b
     │       ╱
     │     ╱           e        V = {a, b, c, d, e}
     │   ╱                      E = {{a, b}, {a, c}, {b, c}, {c, d}}
     c ─────── d                n = 5, m = 4

Here a and b are adjacent, the edge {c, d} is incident to c and to d, N(c) = {a, b, d}, and e is isolated.

V = {"a", "b", "c", "d", "e"}
E = {frozenset(p) for p in [("a", "b"), ("a", "c"), ("b", "c"), ("c", "d")]}   # unordered pairs

def neighbors(v):
    return {w for e in E if v in e for w in e if w != v}

print(sorted(neighbors("c")))                       # ['a', 'b', 'd']
print(frozenset({"b", "a"}) in E)                   # True: {a, b} and {b, a} are the same edge
print([v for v in sorted(V) if not neighbors(v)])   # ['e']   isolated vertices
print(len(E), len(V) * (len(V) - 1) // 2)           # 4 10    m versus the maximum C(n, 2)

Key takeaways

A graph is a pair (V, E): vertices and the edges between them. Only the connections matter, not the drawing.
A simple graph has no loops and no multiple edges, so it has at most C(n, 2) edges.
Adjacent vertices share an edge. An edge is incident to its endpoints. N(v) is the set of neighbors of v.
Real-world graphs are usually sparse, and this drives the choice of data structures (8.2).

Practice

(Beginner) Draw the graph with V = {1, 2, 3, 4, 5, 6} where {i, j} is an edge whenever i ≠ j and i divides j. List N(1), N(6), and any isolated vertices.

(Intermediate) How many different simple graphs can be built on the labeled vertex set {1, …, n}? How many of them have exactly k edges? Hint: each of the C(n, 2) possible edges is either present or absent (5.1).

(Interview) You are modeling a city's bike-sharing system to answer "which stations are reachable from here within 10 minutes". What are the vertices and edges, are the edges weighted, and is the graph simple? Hint: think about what a trip looks like, whether two different routes can join the same pair of stations, and whether a trip from a station back to itself matters.

Directed and Undirected Graphs

Why. Some relationships are symmetric: if Ana is Ben's sibling, Ben is Ana's sibling. Others are not: Ana may follow Ben on a social network without Ben following her back. A web page can link to another without a link in return, and a package can depend on a library that does not depend on it. Directed graphs model one-way relationships, and they need their own versions of degree, connectivity and paths.

What. A directed graph (or digraph) G = (V, E) has a set of directed edges (arcs), which are ordered pairs (u, v), written u → v. The vertex u is the tail (initial vertex) and v is the head (terminal vertex).

A directed graph on V is the same thing as a relation on V (2.4), and an undirected simple graph is the same thing as a symmetric, irreflexive relation. Replacing every arc u → v by the undirected edge {u, v} gives the underlying undirected graph.

	Undirected graph	Directed graph
Edge	Unordered pair `{u, v}`	Ordered pair `(u, v)`
Picture	`u ──── v`	`u ───► v`
Neighbors	`N(v)`	Out-neighbors `N⁺(v)` and in-neighbors `N⁻(v)`
Degree	`deg(v)`	Out-degree `deg⁺(v)` and in-degree `deg⁻(v)`
As a relation	Symmetric and irreflexive	Any relation
Typical examples	Friendship, road with two-way traffic, chemical bond	Follows, hyperlinks, dependencies, one-way streets
Maximum edges (simple, no loops)	`n(n − 1)/2`	`n(n − 1)`

How. To decide which kind of graph to use, ask whether the relation is symmetric. If the edge u → v always comes with v → u, an undirected graph is simpler and halves the storage. Otherwise use a directed graph. You can always model an undirected edge as two opposite arcs, which is exactly what most adjacency-list code does (8.2).

Example: a follow graph.

     ana ─────► ben
      ▲  ◄───── │
      │         │         ana → ben, ben → ana   (mutual)
      │         ▼         ben → dev, dev → cleo, cleo → ana
     cleo ◄──── dev

follows = {                       # out-neighbors: who each user follows
    "ana": {"ben"},
    "ben": {"ana", "dev"},
    "cleo": {"ana"},
    "dev": {"cleo"},
}

def followers(user):              # in-neighbors: scan every out-list
    return {u for u, outs in follows.items() if user in outs}

mutual = {frozenset((u, v)) for u, outs in follows.items() for v in outs if u in follows[v]}
underlying = {frozenset((u, v)) for u, outs in follows.items() for v in outs}

print(sorted(followers("ana")))   # ['ben', 'cleo']
print([sorted(e) for e in mutual])            # [['ana', 'ben']]
print(sum(map(len, follows.values())), len(underlying))   # 5 4   two opposite arcs merge into one edge

Key takeaways

Directed edges are ordered pairs u → v. Undirected edges are unordered pairs {u, v}.
A directed graph is a relation on V. An undirected simple graph is a symmetric, irreflexive relation.
Every directed concept splits in two: in- and out-neighbors, in- and out-degree.
Forgetting directions gives the underlying undirected graph, and opposite arcs merge into one edge.

Practice

(Beginner) For the follow graph above, list N⁺(v) and N⁻(v) for every vertex. Which user follows the most people, and which has the most followers?

(Intermediate) How many directed graphs without loops are there on n labeled vertices? How many with loops allowed? How many of the loop-free ones are symmetric? Hint: count the possible arcs, then apply the product rule (5.1).

(Interview) A social network stores only out-lists (who I follow). The product team wants a "followers" page and a "mutual friends" badge. What would you precompute, and how much extra storage does it cost? Hint: the reverse graph has the same number of arcs. A mutual pair is an arc whose reverse is also present.

Degree and Handshaking Lemma

Why. The degree of a vertex is the simplest measure of how connected it is: a hub airport, a popular user, a heavily imported module. Degrees also obey a counting law, the handshaking lemma, which rules out many graphs before you ever try to draw them, and which is behind many proofs in this chapter.

What. The degree deg(v) of a vertex in an undirected graph is the number of edges incident to it, with each loop counted twice. A vertex of degree 0 is isolated and a vertex of degree 1 is pendant (a leaf). δ(G) and Δ(G) denote the minimum and maximum degree. A graph is k-regular if every vertex has degree k. The degree sequence lists all the degrees in non-increasing order.

Handshaking lemma. In every undirected graph,

  Σ_{v ∈ V} deg(v) = 2m

Proof. Count the pairs (vertex, incident edge) in two ways (double counting, 5.1). Counting by vertex gives Σ deg(v). Counting by edge gives 2 for every edge, because each edge has two ends (a loop has both ends at the same vertex, which is why it counts twice). The two counts are equal.

Corollary. Every graph has an even number of vertices of odd degree. Proof. The sum of the even degrees is even, and 2m is even, so the sum of the odd degrees is even. A sum of odd numbers is even only if there is an even number of them.

Directed version. Each arc contributes 1 to the out-degree of its tail and 1 to the in-degree of its head, so

  Σ_{v ∈ V} deg⁺(v) = Σ_{v ∈ V} deg⁻(v) = m

Example. Can 7 people each shake hands with exactly 3 others? The degree sum would be 7 · 3 = 21, which is odd. So it is impossible, however the handshakes are arranged.

Which sequences are degree sequences? An even sum is necessary but not sufficient: (3, 3, 3, 1) has sum 10, yet no simple graph has it, because the three vertices of degree 3 must each be adjacent to all three other vertices, including the vertex of degree 1. The Havel–Hakimi algorithm decides the question. Remove the largest degree d, subtract 1 from the next d degrees (connect that vertex to the d vertices that need edges most), and repeat. The original sequence is graphic (realizable by a simple graph) if and only if the process ends with all zeros.

def degrees(n, edges):
    deg = [0] * n
    for u, v in edges:
        deg[u] += 1
        deg[v] += 1                                # a loop (u == v) correctly adds 2
    return deg

edges = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)]
deg = degrees(5, edges)
print(deg, sum(deg), 2 * len(edges))               # [2, 2, 3, 2, 1] 10 10
print(sum(d % 2 for d in deg))                     # 2   odd-degree vertices: always an even count

def is_graphic(seq):
    """Havel–Hakimi: can a simple graph have exactly these degrees?"""
    seq = sorted(seq, reverse=True)
    while seq and seq[0] > 0:
        d, seq = seq[0], seq[1:]
        if d > len(seq):
            return False                           # not enough other vertices to connect to
        seq = [x - 1 for x in seq[:d]] + seq[d:]   # join the removed vertex to the d largest
        if min(seq) < 0:
            return False
        seq.sort(reverse=True)
    return True

print(is_graphic([3, 3, 2, 2, 2]), is_graphic([3, 3, 3, 1]), is_graphic([3] * 7))   # True False False

Key takeaways

deg(v) counts incident edges, and a loop counts twice.
Handshaking lemma: Σ deg(v) = 2m. In a digraph, the in-degrees and the out-degrees each sum to m.
The number of odd-degree vertices is always even.
An even degree sum is necessary but not sufficient for a sequence to be graphic. Havel–Hakimi decides it.

Practice

(Beginner) A graph has degree sequence (4, 3, 3, 2, 2). How many edges does it have? Is there a graph with degree sequence (5, 3, 3, 2, 2) on 5 vertices?

(Intermediate) Prove that every simple graph with at least 2 vertices has two vertices of the same degree. Hint: the possible degrees are 0, …, n − 1, but 0 and n − 1 cannot both occur. Apply the pigeonhole principle (5.4).

(Interview) The "friendship paradox" says that, on average, your friends have more friends than you do. Make this precise: compare the average degree with the average degree of a randomly chosen endpoint of a random edge. Hint: the second average is Σ deg(v)² / Σ deg(v). Compare it with Σ deg(v) / n, using the fact that a variance is non-negative (7.3).

Special Graphs (Complete, Cycle, Wheel, Hypercube)

Why. A few families of graphs show up again and again: as extreme cases in theorems, as counterexamples, as test inputs for algorithms, and as real network topologies. Knowing their vertex counts, edge counts and degrees by heart saves a lot of work.

What.

The complete graph Kₙ has n vertices and an edge between every pair. It is the densest simple graph.
The cycle Cₙ (n ≥ 3) has vertices v₁, …, vₙ and edges {v₁, v₂}, {v₂, v₃}, …, {vₙ₋₁, vₙ}, {vₙ, v₁}.
The path Pₙ is Cₙ with one edge removed: n vertices in a line.
The wheel Wₙ (n ≥ 3) is Cₙ plus a hub vertex adjacent to all n vertices of the cycle.
The n-cube (hypercube) Qₙ has the 2ⁿ bit strings of length n as vertices. Two strings are adjacent when they differ in exactly one bit.

     K₄                  C₅                  W₅

   a ──── b               1                   1
   │ ╲  ╱ │             ╱   ╲               ╱ │ ╲
   │  ╳   │            5     2             5 ─ h ─ 2
   │ ╱  ╲ │             ╲   ╱              ╲ ╱  ╲ ╱
   c ──── d              4 ─ 3              4 ── 3

     Q₃
          110 ─────────── 111
         ╱ │             ╱ │
      010 ─────────── 011  │
       │   │           │   │
       │  100 ─────────│─ 101
       │ ╱             │ ╱
      000 ─────────── 001

(In W₅, the hub h is joined to all five rim vertices 1, …, 5.)

Graph	Vertices	Edges	Degrees
`Kₙ`	`n`	`n(n − 1)/2`	`n − 1` (regular)
`Cₙ`	`n`	`n`	2 (regular)
`Pₙ`	`n`	`n − 1`	1 at the two ends, 2 elsewhere
`Wₙ`	`n + 1`	`2n`	3 on the rim, `n` at the hub
`Qₙ`	`2ⁿ`	`n · 2ⁿ⁻¹`	`n` (regular)

Each edge count follows from the handshaking lemma. For example, Qₙ has 2ⁿ vertices of degree n, so 2m = n · 2ⁿ.

Hypercubes recursively. Qₙ is two copies of Qₙ₋₁, one with 0 prepended to every label and one with 1 prepended, plus an edge joining each vertex to its twin. This recursive structure made hypercubes a classic interconnection network for parallel computers: 2ⁿ processors, each with only n links, and any processor can reach any other in at most n hops, because the distance between two vertices is their Hamming distance.

from itertools import combinations

def complete(n):
    return list(combinations(range(n), 2))

def cycle(n):
    return [(i, (i + 1) % n) for i in range(n)]

def wheel(n):                                       # rim 0 … n−1, hub n
    return cycle(n) + [(i, n) for i in range(n)]

def hypercube(n):
    # u and v differ in exactly one bit  <=>  u XOR v is a power of two
    return [(u, u ^ (1 << b)) for u in range(2 ** n) for b in range(n) if u < u ^ (1 << b)]

for name, edges in [("K6", complete(6)), ("C6", cycle(6)), ("W6", wheel(6)), ("Q4", hypercube(4))]:
    print(name, len(edges))
# K6 15
# C6 6
# W6 12
# Q4 32

print(bin(0b0110 ^ 0b0011).count("1"))             # 2   distance in Q4 between 0110 and 0011

Key takeaways

Kₙ: every pair adjacent, n(n − 1)/2 edges. Cₙ: a ring of n edges. Wₙ: a cycle plus a hub, 2n edges.
Qₙ: bit strings joined when they differ in one bit. It has 2ⁿ vertices, n · 2ⁿ⁻¹ edges, and is n-regular.
Qₙ is built from two copies of Qₙ₋₁, and the distance between two vertices is their Hamming distance.
The handshaking lemma gives every edge count in the table.

Practice

(Beginner) How many vertices and edges do K₁₀, C₁₀, W₁₀ and Q₅ have?

(Intermediate) For which n is Kₙ regular, Wₙ regular, and Cₙ equal to Kₙ? Prove that Qₙ has n · 2ⁿ⁻¹ edges by induction on n (3.2), using the recursive construction.

(Interview) In a hypercube network of 2ⁿ processors, design a routing rule that each processor can apply locally, using only the destination address, to forward a message along a shortest path. How many different shortest paths are there between two processors at distance d? Hint: fix one differing bit per hop. The differing bits can be fixed in any order.

Bipartite Graphs

Why. Many systems have two kinds of objects, and edges only run between the kinds: workers and tasks, users and products, students and courses, documents and words. These graphs have special structure. They are exactly the graphs that can be 2-colored, they have no odd cycles, and their matching problems (8.6) have elegant solutions.

What. A graph is bipartite if V can be split into two disjoint sets V₁ and V₂ (the parts) so that every edge has one endpoint in V₁ and the other in V₂. Equivalently, the vertices can be colored with two colors so that every edge joins different colors.

The complete bipartite graph K_{m,n} has parts of sizes m and n and all mn edges between them.

   K₂,₃                     C₆ (bipartite)              C₅ (not bipartite)

    x₁          x₂             1 ── 2                         1
    ├──── y₁ ───┤            ╱        ╲                    ╱     ╲
    ├──── y₂ ───┤           6          3                  5        2
    └──── y₃ ───┘            ╲        ╱                    ╲      ╱
                               5 ── 4                        4 ── 3

   parts {x₁, x₂}, {y₁, y₂, y₃}   parts {1, 3, 5}, {2, 4, 6}   1, 2, 3, 4, 5 cannot alternate

Theorem. A graph is bipartite if and only if it contains no cycle of odd length.

Proof. (⇒) Walking along a cycle alternates between the two parts, so you return to the starting part only after an even number of steps. (⇐) Treat each connected component (8.3) separately. Pick a vertex r and color each vertex by the parity of its distance from r. If some edge {u, v} joined two vertices of the same parity, then the shortest paths from r to u and to v, together with that edge, would form a closed walk of odd length, and every odd closed walk contains an odd cycle (8.3). This contradicts the assumption, so the coloring is proper.

How. The proof is an algorithm. Run breadth-first search (8.4) from an uncolored vertex, give each new vertex the opposite color of the vertex that discovered it, and report a conflict if an edge joins two vertices of the same color. It runs in O(n + m) time.

from collections import deque

def two_color(adj):
    """Return a 2-coloring {v: 0/1}, or None if the graph has an odd cycle."""
    color = {}
    for start in adj:                                # every component needs its own start
        if start in color:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for w in adj[u]:
                if w not in color:
                    color[w] = 1 - color[u]          # opposite side of u
                    queue.append(w)
                elif color[w] == color[u]:
                    return None                      # edge inside one side: odd cycle exists
    return color

def cycle_adj(n):
    return {i: [(i - 1) % n, (i + 1) % n] for i in range(n)}

print(two_color(cycle_adj(6)))                       # {0: 0, 5: 1, 1: 1, 4: 0, 2: 0, 3: 1}
print(two_color(cycle_adj(5)))                       # None

Key takeaways

Bipartite means the vertices split into two parts and every edge crosses between them, which is the same as being 2-colorable.
K_{m,n} has mn edges. Cₙ is bipartite exactly when n is even, and Qₙ is always bipartite (split by the parity of the number of 1s).
A graph is bipartite if and only if it has no odd cycle.
BFS 2-coloring tests bipartiteness in O(n + m).

Practice

(Beginner) Which of these are bipartite: K₃, C₈, W₄, Q₃, K_{1,5}? Give the parts or an odd cycle.

(Intermediate) Prove that a bipartite graph with n vertices has at most ⌊n²/4⌋ edges. When is the bound attained? Hint: with parts of size k and n − k, there are at most k(n − k) edges.

(Interview) You are given n people and a list of pairs who refuse to be on the same team. Decide whether everyone can be split into two teams. What do you report when it is impossible? Hint: this is a bipartiteness test. When it fails, the two BFS paths to the conflicting edge give an odd cycle of mutual dislike, a short certificate.

Subgraphs and Complements

Why. It is often useful to look at part of a graph: the employees in one department, the roads that survive a flood, a network with one router removed. Other problems are about the edges that are not there. The complement turns "pairs that do not conflict" into ordinary edges, so a question about missing edges becomes a question about edges.

What.

A subgraph of G = (V, E) is a graph H = (W, F) with W ⊆ V and F ⊆ E, where every edge in F has both endpoints in W.
A spanning subgraph keeps all the vertices: W = V.
The induced subgraph G[W] keeps the vertices in W and every edge of G between them.
G − v deletes a vertex and its incident edges. G − e deletes an edge only. G + e adds an edge.
The union G₁ ∪ G₂ has vertex set V₁ ∪ V₂ and edge set E₁ ∪ E₂.
The complement Ḡ has the same vertices as G, and {u, v} is an edge of Ḡ exactly when it is not an edge of G (for u ≠ v).

Two important kinds of subgraph: a clique is a set of vertices that are pairwise adjacent (an induced complete subgraph), and an independent set is a set of vertices with no edges between them. A clique in G is an independent set in Ḡ, and vice versa.

Since every pair of distinct vertices is an edge of exactly one of G and Ḡ,

  m(G) + m(Ḡ) = C(n, 2)        and        deg_Ḡ(v) = n − 1 − deg_G(v)

A graph isomorphic (8.2) to its own complement is self-complementary. P₄ and C₅ are the smallest examples: the complement of a pentagon is a pentagram, which is another 5-cycle.

   G = C₅ (pentagon)          Ḡ (pentagram, redrawn as a cycle)
          0                            0
        ╱   ╲                        ╱   ╲
       4     1                      3     2
        ╲   ╱                        ╲   ╱
         3 ─ 2                        1 ─ 4

   edges of Ḡ: {0,2}, {0,3}, {1,3}, {1,4}, {2,4}   =   the 5-cycle 0-2-4-1-3-0

from itertools import combinations

def complement(vertices, edges):
    E = {frozenset(e) for e in edges}
    return [p for p in combinations(sorted(vertices), 2) if frozenset(p) not in E]

def induced(edges, W):
    return [(u, v) for u, v in edges if u in W and v in W]

C5 = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
print(complement(range(5), C5))                 # [(0, 2), (0, 3), (1, 3), (1, 4), (2, 4)]
print(induced(C5, {0, 1, 2}))                   # [(0, 1), (1, 2)]   a path, not a triangle

K4 = list(combinations(range(4), 2))
print(len(K4) + len(complement(range(4), K4)))  # 6 = C(4, 2): the complement of K4 has no edges

Key takeaways

A subgraph takes some vertices and some of the edges among them. An induced subgraph takes all edges among the chosen vertices.
A spanning subgraph keeps every vertex.
The complement swaps edges and non-edges: m(G) + m(Ḡ) = C(n, 2).
Cliques in G are independent sets in Ḡ.

Practice

(Beginner) How many subgraphs does K₃ have (count subgraphs on every non-empty vertex subset)? How many of them are induced?

(Intermediate) Prove that a self-complementary graph on n vertices has n ≡ 0 or n ≡ 1 (mod 4). Hint: G and Ḡ have the same number of edges, so m = n(n − 1)/4 must be an integer.

(Interview) Prove that among any 6 people there are either 3 mutual friends or 3 mutual strangers, so that every graph on 6 vertices contains a triangle in G or in Ḡ. Hint: fix one person. Of the 5 others, at least 3 are friends or at least 3 are strangers (pigeonhole, 5.4). Look at the edges among those 3.

8.2 Graph Representation and Isomorphism

A graph is an abstract object, but a program needs a concrete data structure. This subchapter covers the three standard representations and their trade-offs, then asks when two differently drawn or differently stored graphs are really the same graph.

Adjacency Lists

Why. Almost every graph algorithm repeats one step: "for each neighbor w of v, do something". The representation should make that step fast and should not waste memory on the edges that are absent, because real graphs are sparse. An adjacency list does both.

What. An adjacency list stores, for each vertex v, a list of its neighbors (for a directed graph, its out-neighbors). In an undirected graph, the edge {u, v} appears twice: v in the list of u and u in the list of v. In a weighted graph, each entry is a pair (neighbor, weight).

     a ─────── b             a: [b, c]
     │       ╱               b: [a, c]
     │     ╱                 c: [a, b, d]
     │   ╱                   d: [c]
     c ─────── d             e: []           total entries: 2m = 8
                e

The total size is n lists plus 2m entries (m entries for a digraph), so the space is Θ(n + m).

Operation	Cost with adjacency lists
Space	`Θ(n + m)`
Iterate over the neighbors of `v`	`Θ(deg v)`, optimal
Test whether `{u, v}` is an edge	`O(deg u)` with lists, expected `O(1)` with hash sets
Iterate over all edges	`Θ(n + m)`
Add an edge	`O(1)`
Remove an edge	`O(deg u + deg v)` with lists, expected `O(1)` with hash sets

Variants.

Dictionary of sets (dict[vertex, set]): vertices can be any hashable value, and edge tests take expected O(1) time. This is the usual choice in Python.
Arrays of arrays: vertices are numbered 0, …, n − 1, and each list is a dynamic array. This is the standard choice in competitive programming and in Java (List<List<Integer>>).
Compressed sparse row (CSR): all lists are concatenated into one array targets, and offsets[v] marks where the list of v starts. It uses two flat arrays and no per-list overhead, which makes it compact and cache-friendly. Graph-processing libraries use it for graphs with billions of edges, at the price of being expensive to modify.

from collections import defaultdict

def adjacency_list(edges, directed=False):
    adj = defaultdict(set)
    for u, v in edges:
        adj[u].add(v)
        if not directed:
            adj[v].add(u)                            # undirected: store both directions
    return adj

adj = adjacency_list([("a", "b"), ("a", "c"), ("b", "c"), ("c", "d")])
adj["e"]                                             # touching a defaultdict key adds the isolated vertex e
print({v: sorted(ns) for v, ns in sorted(adj.items())})
# {'a': ['b', 'c'], 'b': ['a', 'c'], 'c': ['a', 'b', 'd'], 'd': ['c'], 'e': []}
print("d" in adj["c"], sum(len(ns) for ns in adj.values()))   # True 8   (= 2m)

def to_csr(n, arcs):
    """Directed graph on 0..n-1 as two flat arrays: offsets (n + 1 entries) and targets (m entries)."""
    offsets = [0] * (n + 1)
    for u, _ in arcs:
        offsets[u + 1] += 1                          # count the out-degree of each vertex
    for i in range(n):
        offsets[i + 1] += offsets[i]                 # prefix sums: where each list starts
    targets, fill = [0] * len(arcs), offsets[:-1]    # slicing makes fill a copy of the starts
    for u, v in arcs:
        targets[fill[u]] = v
        fill[u] += 1
    return offsets, targets

offsets, targets = to_csr(4, [(0, 1), (0, 2), (2, 3), (1, 2), (3, 0)])
print(offsets, targets)                              # [0, 2, 3, 4, 5] [1, 2, 2, 3, 0]
print(targets[offsets[0]:offsets[1]])                # [1, 2]   out-neighbors of vertex 0

Key takeaways

An adjacency list stores each vertex's neighbors and uses Θ(n + m) space, which suits sparse graphs.
Iterating over neighbors costs Θ(deg v), which is what traversal algorithms (8.4) need.
Use hash sets when you also need fast edge tests, and CSR arrays for very large static graphs.
In an undirected graph, every edge is stored twice.

Practice

(Beginner) Write the adjacency list of W₄ (rim 1, 2, 3, 4, hub h). How many entries does it contain in total?

(Intermediate) Given the adjacency list of a directed graph, build the adjacency list of its reverse (every arc flipped) in O(n + m) time. Then use it to list all vertices with in-degree 0.

(Interview) A road network has 50 million intersections and 120 million road segments, and the graph never changes once loaded. Estimate the memory for CSR with 4-byte integers, and compare it with a dictionary of sets in Python. Hint: CSR needs n + 1 offsets plus 2m targets for undirected edges. A Python object costs tens of bytes.

Adjacency Matrices

Why. Sometimes the most frequent question is "is there an edge between u and v?", and it must be answered in constant time. Sometimes you want to compute with the graph using linear algebra. Both call for a matrix. A matrix also reveals a surprising fact: matrix powers count walks.

What. Number the vertices v₁, …, vₙ. The adjacency matrix is the n × n matrix A with

  aᵢⱼ = 1   if {vᵢ, vⱼ} is an edge
  aᵢⱼ = 0   otherwise

For a multigraph, aᵢⱼ is the number of edges between vᵢ and vⱼ. For a directed graph, aᵢⱼ = 1 when vᵢ → vⱼ, exactly as for the zero-one matrix of a relation (2.4). For a weighted graph, the entry is the weight, and a missing edge is usually stored as ∞ or 0.

     1 ─── 2              1  2  3  4
     │     │          1 [ 0  1  0  1 ]
     │     │          2 [ 1  0  1  0 ]       C₄
     4 ─── 3          3 [ 0  1  0  1 ]
                      4 [ 1  0  1  0 ]

Properties:

An undirected graph has a symmetric matrix. A simple graph has zeros on the diagonal.
The sum of row i is deg(vᵢ). For a digraph, row sums are out-degrees and column sums are in-degrees.
Relabeling the vertices permutes the rows and columns in the same way.

Walks and matrix powers. A walk of length k is a sequence of k edges where each edge starts where the previous one ended (8.3).

Theorem. (Aᵏ)ᵢⱼ is the number of walks of length k from vᵢ to vⱼ.

Proof by induction on k (3.2). For k = 1 this is the definition of A. Suppose it holds for k. A walk of length k + 1 from vᵢ to vⱼ is a walk of length k from vᵢ to some vₗ, followed by an edge from vₗ to vⱼ. Summing over l gives Σₗ (Aᵏ)ᵢₗ · aₗⱼ = (Aᵏ⁺¹)ᵢⱼ.

Two consequences:

(A²)ᵢᵢ = deg(vᵢ), because a closed walk of length 2 goes out along an edge and comes straight back.
A triangle gives 6 closed walks of length 3 (3 starting vertices times 2 directions), so the number of triangles is trace(A³)/6.

	Adjacency list	Adjacency matrix
Space	`Θ(n + m)`	`Θ(n²)`
Edge test `{u, v}`	`O(deg u)` or expected `O(1)` with hashing	`O(1)`
Iterate over neighbors of `v`	`Θ(deg v)`	`Θ(n)`
Iterate over all edges	`Θ(n + m)`	`Θ(n²)`
Add or remove an edge	`O(1)` to `O(deg)`	`O(1)`
Best for	Sparse graphs, traversals	Dense graphs, frequent edge tests, linear algebra

As a rule of thumb, use a matrix when m is a constant fraction of n², or when n is small (a few thousand vertices at most). One million vertices would need 10¹² entries.

def matmul(X, Y):
    return [[sum(X[i][k] * Y[k][j] for k in range(len(Y))) for j in range(len(Y[0]))]
            for i in range(len(X))]

def adjacency_matrix(n, edges):
    A = [[0] * n for _ in range(n)]
    for u, v in edges:
        A[u][v] = A[v][u] = 1                        # undirected: symmetric
    return A

C4 = adjacency_matrix(4, [(0, 1), (1, 2), (2, 3), (3, 0)])
A2 = matmul(C4, C4)
print(A2)            # [[2, 0, 2, 0], [0, 2, 0, 2], [2, 0, 2, 0], [0, 2, 0, 2]]
# Diagonal = degrees. Two walks of length 2 from vertex 0 to vertex 2 (via 1 or via 3).

K4 = adjacency_matrix(4, [(i, j) for i in range(4) for j in range(i + 1, 4)])
A3 = matmul(matmul(K4, K4), K4)
print(sum(A3[i][i] for i in range(4)) // 6)        # 4   triangles in K4: trace(A^3) / 6

Key takeaways

aᵢⱼ = 1 when vᵢ and vⱼ are adjacent. An undirected graph has a symmetric matrix, and the row sums are the degrees.
Θ(n²) space and O(1) edge tests: use a matrix for small or dense graphs.
(Aᵏ)ᵢⱼ counts walks of length k from vᵢ to vⱼ, and trace(A³)/6 counts triangles.
Relabeling vertices permutes the rows and columns of A simultaneously.

Practice

(Beginner) Write the adjacency matrix of K_{1,3} with the center listed first. Compute A² and interpret its entries.

(Intermediate) Prove that a graph is bipartite with parts {v₁, …, vₖ} and {vₖ₊₁, …, vₙ} exactly when its adjacency matrix has the block form [[0, B], [Bᵀ, 0]]. Use this to show that (Aᵏ)ᵢᵢ = 0 for every odd k in a bipartite graph.

(Interview) You must count triangles in a social graph with 10⁸ vertices and 10¹⁰ edges. Why is computing trace(A³) with dense matrices hopeless, and what would you do instead? Hint: for each edge {u, v}, intersect the neighbor sets of u and v. Orienting each edge from lower to higher degree keeps the sets small.

Incidence Matrices

Why. An adjacency matrix records vertex–vertex relationships. Some questions are about vertex–edge relationships instead: which edges meet at a junction, how much flow enters and leaves a node, which wires a current passes through. The incidence matrix records exactly that. It is the basic object in electrical network analysis (Kirchhoff's laws) and in the linear-programming view of flows (8.6).

What. Number the vertices v₁, …, vₙ and the edges e₁, …, eₘ. The incidence matrix is the n × m matrix M with

  mᵢⱼ = 1   if edge eⱼ is incident to vertex vᵢ
  mᵢⱼ = 0   otherwise

Each column has exactly two 1s, one for each endpoint of the edge. The sum of row i is deg(vᵢ). Counting the 1s in M by rows and by columns is exactly the double counting in the handshaking lemma: Σ deg(vᵢ) = 2m. (Conventions for loops vary: some texts put a 2 in the column, others a 1.)

For a directed graph, or an undirected graph with an arbitrary orientation chosen for each edge, the oriented incidence matrix B has −1 at the tail of each arc and +1 at its head. Each column then sums to 0, and

  B · Bᵀ = D − A = L

where D is the diagonal matrix of degrees. L is the Laplacian matrix. It does not depend on the orientation chosen, and Kirchhoff's matrix-tree theorem uses it to count spanning trees (9.4).

                       e₁  e₂  e₃  e₄
     a ──e₁── b     a [ 1   1   0   0 ]      e₁ = {a, b}
     │       ╱      b [ 1   0   1   0 ]      e₂ = {a, c}
    e₂    e₃        c [ 0   1   1   1 ]      e₃ = {b, c}
     │   ╱          d [ 0   0   0   1 ]      e₄ = {c, d}
     c ──e₄── d

V = ["a", "b", "c", "d"]
E = [("a", "b"), ("a", "c"), ("b", "c"), ("c", "d")]

M = [[1 if v in e else 0 for e in E] for v in V]
print([sum(row) for row in M])                      # [2, 2, 3, 1]   row sums are degrees
print([sum(col) for col in zip(*M)])                # [2, 2, 2, 2]   every edge has two ends

# Oriented incidence matrix: -1 at the tail, +1 at the head (orientation chosen as listed)
B = [[-1 if v == e[0] else 1 if v == e[1] else 0 for e in E] for v in V]
L = [[sum(B[i][k] * B[j][k] for k in range(len(E))) for j in range(len(V))] for i in range(len(V))]
for row in L:
    print(row)
# [2, -1, -1, 0]
# [-1, 2, -1, 0]
# [-1, -1, 3, -1]
# [0, 0, -1, 1]      L = D - A: degrees on the diagonal, -1 for each edge

Key takeaways

The incidence matrix is n × m, with a 1 where a vertex meets an edge.
Each column has two 1s and each row sums to the degree, which is the handshaking lemma in matrix form.
The oriented version has −1 and +1 in each column, and B · Bᵀ is the Laplacian D − A.
It uses Θ(nm) space, so it is a tool for theory and linear algebra rather than a general-purpose data structure.

Practice

(Beginner) Write the incidence matrix of C₄ with edges e₁ = {1, 2}, e₂ = {2, 3}, e₃ = {3, 4}, e₄ = {4, 1}.

(Intermediate) Show that the rows of an oriented incidence matrix sum to the zero vector, so its rank is at most n − 1. Show also that every row sum of the Laplacian L is 0.

(Interview) In a flow network (8.6), let f be the vector of flows on the arcs and B the oriented incidence matrix. What does the vector B · f represent, and how would you state "flow is conserved at every vertex except the source and the sink" as a linear constraint? Hint: entry i of B · f is the flow into vᵢ minus the flow out of it.

Graph Isomorphism

Why. The same graph can be drawn in many ways and stored with many labelings. Two chemists may draw the same molecule differently, and two programs may number the same network's routers differently. We need a precise way to say that two graphs have the same structure, regardless of names and pictures.

What. Graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) are isomorphic, written G₁ ≅ G₂, if there is a bijection f : V₁ → V₂ (2.2) such that

  {u, v} ∈ E₁   ⟺   {f(u), f(v)} ∈ E₂        for all u, v ∈ V₁

Such an f is an isomorphism. It renames the vertices so that edges become edges and non-edges become non-edges. Isomorphism is an equivalence relation on graphs (2.5), and each equivalence class is an "unlabeled graph". An isomorphism from a graph to itself is an automorphism, which describes a symmetry of the graph.

In matrix terms, G₁ ≅ G₂ exactly when A₂ = P · A₁ · Pᵀ for some permutation matrix P: relabeling permutes rows and columns together.

Example. Both drawings below show the same 4-cycle.

     G₁                 G₂
   1 ──── 2           a      b
   │      │           │ ╲  ╱ │         f(1) = a,  f(2) = c,  f(3) = b,  f(4) = d
   │      │           │  ╳   │         {1,2} ↦ {a,c}   {2,3} ↦ {c,b}
   4 ──── 3           │ ╱  ╲ │         {3,4} ↦ {b,d}   {4,1} ↦ {d,a}
                      c      d

(In G₂, the two diagonals cross without meeting, and G₂ has edges {a, c}, {a, d}, {b, c}, {b, d}.) All four edges of G₁ map to edges of G₂, and both graphs have 4 edges, so the two non-edges {1, 3} and {2, 4} map to the two non-edges {a, b} and {c, d}.

How.

To prove G₁ ≅ G₂, give an explicit bijection and check every edge.
To disprove it, find a property that every isomorphism preserves but the two graphs do not share (the next topic, Graph Invariants).

Trying all n! bijections works only for tiny graphs. Checking degrees first prunes most of them: an isomorphism must map each vertex to one of the same degree. The graph isomorphism problem has an unusual status. It is in NP, it is not known to be in P, and it is not believed to be NP-complete (10.3). Babai's algorithm (2015) solves it in quasi-polynomial time exp(O((log n)ᶜ)). In practice, tools such as nauty compute a canonical labeling (one representative of each isomorphism class), which handles graphs with millions of vertices.

from itertools import permutations

def find_isomorphism(n, E1, E2):
    """Brute force over bijections of {0, ..., n-1}, pruned by degrees."""
    A = {frozenset(e) for e in E1}
    B = {frozenset(e) for e in E2}
    if len(A) != len(B):
        return None
    deg1 = [sum(v in e for e in A) for v in range(n)]
    deg2 = [sum(v in e for e in B) for v in range(n)]
    for f in permutations(range(n)):
        if any(deg1[v] != deg2[f[v]] for v in range(n)):
            continue                                 # degrees must be preserved
        # f maps edges injectively into B and |A| = |B|, so non-edges also map to non-edges
        if all(frozenset(f[v] for v in e) in B for e in A):
            return dict(enumerate(f))
    return None

pentagon  = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
pentagram = [(0, 2), (2, 4), (4, 1), (1, 3), (3, 0)]
print(find_isomorphism(5, pentagon, pentagram))     # {0: 0, 1: 2, 2: 4, 3: 1, 4: 3}

path_P4 = [(0, 1), (1, 2), (2, 3)]
star    = [(0, 1), (0, 2), (0, 3)]
print(find_isomorphism(4, path_P4, star))           # None   degrees (1, 2, 2, 1) vs (3, 1, 1, 1)

Key takeaways

An isomorphism is a bijection of vertices that preserves adjacency and non-adjacency.
Isomorphic graphs are the same graph with different names. The drawing is irrelevant.
Prove isomorphism with an explicit bijection. Disprove it with an invariant.
No polynomial-time algorithm is known, but canonical labeling is fast in practice.

Practice

(Beginner) Show that C₅ is isomorphic to its complement by writing out the bijection and checking all five edges.

(Intermediate) There are 11 non-isomorphic simple graphs on 4 vertices. Draw them, grouping by the number of edges (0 to 6). Hint: the counts by number of edges are 1, 1, 2, 3, 2, 1, 1. Complementation pairs up k edges with 6 − k.

(Interview) A chemistry database stores millions of molecules as graphs and must reject duplicates on insert. Hashing the edge list fails because the same molecule can be numbered differently. How would you design the duplicate check? Hint: compute a cheap invariant hash (such as refined degree colors, next topic) to find candidates, then confirm with an exact isomorphism test or a canonical form.

Graph Invariants

Why. Searching for an isomorphism can take a very long time, but proving that two graphs are not isomorphic is often quick: count something, and if the counts differ, you are done. Invariants are also the features used to fingerprint and classify graphs.

What. A graph invariant is a property that is the same for any two isomorphic graphs. If G₁ and G₂ differ in some invariant, they are not isomorphic. Equal invariants prove nothing on their own, unless the invariant is complete (determines the graph up to isomorphism), and no complete invariant is known that is efficient to compute.

Invariant	Cost to compute	Notes
Number of vertices, number of edges	`O(1)`	The first check
Degree sequence	`O(n + m)`	Very effective in practice
Number of connected components (8.3)	`O(n + m)`
Bipartite or not (8.1)	`O(n + m)`	Presence of odd cycles
Number of triangles, or of `k`-cycles for fixed `k`	Polynomial
Distances: diameter, girth (8.3)	Polynomial
Spectrum (eigenvalues of `A`)	Polynomial	Different graphs can share it (cospectral graphs)
Planarity (8.5)	`O(n)`
Chromatic number (8.5)	NP-hard

Equal degree sequences are not enough. The 6-cycle C₆ and two disjoint triangles 2K₃ both have six vertices of degree 2. But C₆ is connected and bipartite with no triangles, while 2K₃ is disconnected and has two triangles. Similarly, the star K_{1,4} and C₄ plus an isolated vertex have the same eigenvalues {2, 0, 0, 0, −2}, but different degree sequences.

        C₆                   2K₃
      1 ── 2               1       4
    ╱        ╲            ╱ ╲     ╱ ╲
   6          3          2 ─ 3   5 ─ 6
    ╲        ╱
      5 ── 4             degree sequence (2, 2, 2, 2, 2, 2) in both graphs

Color refinement. A strong but cheap invariant comes from refining degrees. Give every vertex the same color. Then repeatedly recolor each vertex by the pair (its color, the multiset of its neighbors' colors). After a few rounds, compare the histograms of colors. This is the Weisfeiler–Leman test (1-WL). It distinguishes almost all pairs of random graphs, and it is the basis of graph neural networks. It fails on regular graphs of the same degree and size, such as C₆ and 2K₃, because every vertex always looks the same as every other.

from collections import Counter

def wl_histograms(adj1, adj2, rounds=3):
    """Color refinement on two graphs with a shared palette, so that colors are comparable."""
    graphs = [adj1, adj2]
    colors = [{v: 0 for v in g} for g in graphs]
    for _ in range(rounds):
        sigs = [{v: (c[v], tuple(sorted(c[w] for w in g[v]))) for v in g}   # own color + neighbors' colors
                for g, c in zip(graphs, colors)]
        palette = {s: i for i, s in enumerate(sorted(set(sigs[0].values()) | set(sigs[1].values())))}
        colors = [{v: palette[s[v]] for v in s} for s in sigs]
    return [sorted(Counter(c.values()).items()) for c in colors]

def adj_from(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, []).append(v)
        adj.setdefault(v, []).append(u)
    return adj

def triangles(adj):
    return sum(len(set(adj[u]) & set(adj[v])) for u in adj for v in adj[u]) // 6

H1 = adj_from([(0, 1), (1, 2), (2, 0), (2, 3), (3, 4)])            # triangle with a tail
H2 = adj_from([(0, 1), (1, 2), (2, 3), (3, 0), (3, 4)])            # square with a tail
print(sorted(len(a) for a in H1.values()) == sorted(len(a) for a in H2.values()))   # True   same degrees
h1, h2 = wl_histograms(H1, H2)
print(h1 == h2)                                                    # False  refinement tells them apart

C6  = adj_from([(i, (i + 1) % 6) for i in range(6)])
twoK3 = adj_from([(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3)]) # two disjoint triangles
h1, h2 = wl_histograms(C6, twoK3)
print(h1 == h2, triangles(C6), triangles(twoK3))                   # True 0 2   refinement fails, triangles succeed

Key takeaways

An invariant is preserved by every isomorphism. Different values prove non-isomorphism, and equal values prove nothing.
Check cheap invariants first: n, m, the degree sequence, components, bipartiteness, triangles.
C₆ and 2K₃ have the same degree sequence but are not isomorphic.
Color refinement (1-WL) is a fast, strong invariant, but it cannot separate regular graphs with the same degree and size.

Practice

(Beginner) Prove that K_{3,3} and the triangular prism (two triangles a₁a₂a₃ and b₁b₂b₃ plus the edges aᵢbᵢ) are not isomorphic, although both are 3-regular with 6 vertices.

(Intermediate) Find two connected, non-isomorphic graphs with the same degree sequence, and name an invariant that distinguishes them. Hint: start from H1 and H2 above, or try 6 vertices with one graph bipartite and the other not.

(Interview) A colleague proposes using (n, m, sorted degree sequence) as a dictionary key to group "identical" network topologies. When does this give wrong answers, and how would you make the grouping exact while keeping it fast? Hint: the key is an invariant, not a complete one, so equal keys only make two graphs candidates. Refine the key, then confirm each group with an isomorphism test.

8.3 Connectivity

Connectivity asks whether you can get from one vertex to another, and how robust that ability is. This subchapter defines walks and paths, splits graphs into connected and strongly connected components, and measures how many vertex or edge failures a network can survive.

Walks, Paths, and Cycles

Why. "Can a packet get from router A to router B?" and "Is there a circular dependency?" are questions about moving along edges. To answer them precisely, we need to say what a route is, and whether it may revisit vertices or reuse edges. Different problems need different rules: an Euler circuit (8.4) never reuses an edge, a shortest path never revisits a vertex, and walks in matrix powers (8.2) may do both.

What. A walk of length k from u to v is a sequence of vertices u = v₀, v₁, …, vₖ = v where each consecutive pair {vᵢ₋₁, vᵢ} is an edge. Its length is the number of edges, k. A walk is closed if v₀ = vₖ.

Name	Repeated vertices?	Repeated edges?	Closed?
Walk	Allowed	Allowed	Either
Trail	Allowed	No	Either
Path	No	No	No
Closed walk	Allowed	Allowed	Yes
Circuit (closed trail)	Allowed	No	Yes
Cycle	No, except `v₀ = vₖ`	No	Yes, with length `≥ 3`

Terminology varies between textbooks. Some (Rosen, for example) say "path" for what this table calls a walk and "simple path" for a path. Always check the definitions in use.

Lemma 1. Every walk from u to v contains a path from u to v.

Proof. Among all u–v walks made from the walk's own steps, take a shortest one (well-ordering, 3.2). If it repeated a vertex x, deleting the part between the two visits of x would give a shorter walk, a contradiction. So it repeats no vertex: it is a path.

Lemma 2. Every closed walk of odd length contains a cycle of odd length.

Proof by strong induction on the length. If the closed walk repeats no vertex (apart from its endpoints), it is itself an odd cycle. (A closed walk of length 1 would be a loop, which simple graphs do not have.) Otherwise, split it at a repeated vertex into two shorter closed walks. Their lengths add up to an odd number, so one of them is odd, and by the induction hypothesis it contains an odd cycle. This lemma was used to characterize bipartite graphs in 8.1.

Distances. The distance d(u, v) is the length of a shortest u–v path, or ∞ if there is none. It is a metric: d(u, v) = 0 exactly when u = v, d(u, v) = d(v, u), and d(u, w) ≤ d(u, v) + d(v, w). The diameter of a connected graph is the largest distance between two vertices, and the girth is the length of its shortest cycle.

   a ─── b ─── c
   │     │     │          a, b, e, d, a, b, c   walk (edge {a, b} used twice)
   │     │     │          a, b, c, f, e, b      trail (b visited twice, no edge repeated)
   d ─── e ─── f          a, b, c, f, e         path
                          a, b, e, d, a         cycle of length 4 (the girth)
                          diameter = d(a, f) = d(d, c) = 3

adj = {"a": "bd", "b": "ace", "c": "bf", "d": "ae", "e": "bdf", "f": "ce"}

def classify(seq):
    steps = list(zip(seq, seq[1:]))
    if any(w not in adj[v] for v, w in steps):
        return "not a walk"
    closed = len(seq) > 1 and seq[0] == seq[-1]
    edges = [frozenset(s) for s in steps]
    if len(set(edges)) < len(edges):
        return "closed walk" if closed else "walk"
    inner = seq[:-1] if closed else seq                # the endpoints of a closed walk coincide
    if len(set(inner)) < len(inner):
        return "circuit" if closed else "trail"
    return "cycle" if closed else "path"

for s in ["abedabc", "abcfeb", "abcfe", "abeda", "abcfedeba", "ac"]:
    print(s, classify(s))
# abedabc walk
# abcfeb trail
# abcfe path
# abeda cycle
# abcfedeba closed walk
# ac not a walk

def walk_to_path(walk):
    """Lemma 1 as code: cut out the loop each time a vertex repeats."""
    path, pos = [], {}
    for v in walk:
        if v in pos:
            for w in path[pos[v] + 1:]:
                del pos[w]                              # forget the vertices on the removed loop
            path = path[:pos[v] + 1]
        else:
            pos[v] = len(path)
            path.append(v)
    return "".join(path)

print(walk_to_path("abedabc"))                        # abc

Key takeaways

Walk: anything goes. Trail: no repeated edges. Path: no repeated vertices. Cycle: a closed path of length at least 3.
The length of a walk is its number of edges.
Every u–v walk contains a u–v path, so "reachable by a walk" and "reachable by a path" mean the same thing.
Every odd closed walk contains an odd cycle.
d(u, v) is the length of a shortest path. The diameter is the largest distance and the girth the shortest cycle length.

Practice

(Beginner) In the grid graph above, find a trail from a to f that is not a path, a circuit that is not a cycle (if one exists), and every cycle through a.

(Intermediate) Prove that if every vertex of a graph has degree at least 2, the graph contains a cycle. Hint: consider a longest path v₀, …, vₖ. Where can the other neighbors of vₖ be?

(Interview) A function receives a sequence of node IDs that is supposed to be a route in a network, and must report whether it is a valid walk, a trail, or a path. Write it to run in O(k) time for a route of length k. Hint: store the adjacency lists as hash sets, and track visited vertices and used edges (as unordered pairs) in hash sets.

Connected Components

Why. The first question to ask about a network is whether it is in one piece. Can every user reach every other user? After a cable is cut, which machines can still talk to each other? How many separate islands does this map contain? Connected components answer all of these questions, and many algorithms first split the input into components and then handle each one independently.

What. Write u ~ v if there is a walk (equivalently, by Lemma 1, a path) from u to v. This is an equivalence relation (2.5):

Reflexive: the walk of length 0 goes from v to v.
Symmetric: reverse the walk.
Transitive: join a u–v walk and a v–w walk.

Its equivalence classes are the connected components of the graph. Each component is a maximal connected subgraph: nothing can be added to it without losing connectedness. A graph is connected when it has exactly one component.

   1 ─── 2         4 ─── 5         6 ─── 7
         │                          ╲   ╱
         3                            8

   three components: {1, 2, 3}, {4, 5}, {6, 7, 8}

Facts.

Adding one edge reduces the number of components by at most 1. Starting from n isolated vertices, you therefore need at least n − k edges to end with k components. In particular, a connected graph has m ≥ n − 1 edges, with equality exactly for trees (9.1).
If G is disconnected, its complement Ḡ is connected.

How.

Traversal. Run BFS or DFS (8.4) from an unvisited vertex, label everything it reaches, and repeat. This takes O(n + m) time.
Union–find (disjoint-set forest). Start with every vertex in its own set and, for each edge, merge the sets of its endpoints. This handles edges that arrive one at a time and answers "are u and v connected?" at any moment. With path compression and union by size, each operation takes amortized O(α(n)) time, where α is the inverse Ackermann function, which is at most 4 for any practical n. Kruskal's algorithm (9.4) uses this structure.

class DisjointSets:
    def __init__(self, items):
        self.parent = {x: x for x in items}
        self.size = {x: 1 for x in items}

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:                 # path compression: point straight at the root
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                              # already in the same component
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                           # union by size: hang the smaller tree
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

ds = DisjointSets(range(1, 9))
for u, v in [(1, 2), (2, 3), (4, 5), (6, 7), (7, 8), (8, 6)]:
    ds.union(u, v)

groups = {}
for v in range(1, 9):
    groups.setdefault(ds.find(v), []).append(v)
print(list(groups.values()))                          # [[1, 2, 3], [4, 5], [6, 7, 8]]
print(ds.find(3) == ds.find(5))                       # False
ds.union(3, 4)                                        # a new edge joins two components
print(ds.find(1) == ds.find(5))                       # True

Key takeaways

"There is a path from u to v" is an equivalence relation, and its classes are the connected components.
A connected graph on n vertices has at least n − 1 edges.
Find components with BFS or DFS in O(n + m), or with union–find when edges arrive incrementally.
The complement of a disconnected graph is connected.

Practice

(Beginner) How many components does the graph on {1, …, 12} have, where i and j are adjacent when |i − j| = 4?

(Intermediate) Prove that if G is disconnected, then Ḡ is connected. Hint: take u and v. If they lie in different components of G, they are adjacent in Ḡ. If they lie in the same component, find a vertex w in another component.

(Interview) Given a grid of '1' (land) and '0' (water), count the islands, where land cells are connected horizontally and vertically. Then handle a stream of "turn cell (r, c) into land" updates, reporting the island count after each one. Hint: the grid is an implicit graph. For the stream, use union–find: each new land cell adds one component and each successful union removes one.

Strongly Connected Components

Why. In a directed graph, reachability is not symmetric: a page may link to a site that never links back. The useful notion of "being in the same piece" is mutual reachability. Strongly connected components group the vertices that can all reach one another. They reveal cycles of dependencies, deadlocks among processes waiting on each other, the core of the web graph, and they are the key step in solving 2-SAT (1.1).

What. A directed graph is strongly connected if for every pair u, v there is a directed path from u to v and one from v to u. It is weakly connected if its underlying undirected graph is connected.

Mutual reachability (u ⇝ v and v ⇝ u) is an equivalence relation, and its classes are the strongly connected components (SCCs). Contracting each SCC to a single vertex gives the condensation of the graph, which is always a DAG: if two SCCs could reach each other, they would form one SCC. The condensation shows the "big picture" order of a directed graph, and topologically sorting it (2.5) orders the SCCs.

    a ───► b
    ▲     ╱
    │   ╱
    │  ▼
    c ───► d ◄──► e ───► f ◄─── g

   arcs: a→b, b→c, c→a, c→d, d→e, e→d, e→f, g→f

   condensation:   {a, b, c} ───► {d, e} ───► {f} ◄─── {g}

How. Two classic algorithms find all SCCs in O(n + m) time.

Kosaraju's algorithm. (1) Run DFS (8.4) on the graph and record vertices in order of finishing. (2) Reverse every arc. (3) Take vertices in decreasing finishing time and run a DFS from each unvisited one in the reversed graph. Each such DFS visits exactly one SCC. It works because the vertex that finishes last lies in a source SCC of the condensation. In the reversed graph that SCC becomes a sink, so a search from it cannot leak into other components.
Tarjan's algorithm does it in one DFS pass, using the low-link values described in the next topic.

def strongly_connected_components(adj):
    """Kosaraju's algorithm with explicit stacks (no recursion limit)."""
    order, seen = [], set()
    for s in adj:                                     # pass 1: record finishing order
        if s in seen:
            continue
        seen.add(s)
        stack = [(s, iter(adj[s]))]
        while stack:
            v, it = stack[-1]
            for w in it:
                if w not in seen:
                    seen.add(w)
                    stack.append((w, iter(adj[w])))
                    break
            else:
                stack.pop()
                order.append(v)                       # v is finished: all its descendants are done

    rev = {v: [] for v in adj}
    for v in adj:
        for w in adj[v]:
            rev[w].append(v)

    comp = {}
    for s in reversed(order):                         # pass 2: decreasing finishing time, reversed arcs
        if s in comp:
            continue
        comp[s] = s
        stack = [s]
        while stack:
            v = stack.pop()
            for w in rev[v]:
                if w not in comp:
                    comp[w] = s
                    stack.append(w)
    return comp                                        # vertex -> representative of its SCC

adj = {"a": ["b"], "b": ["c"], "c": ["a", "d"], "d": ["e"], "e": ["d", "f"], "f": [], "g": ["f"]}
comp = strongly_connected_components(adj)
sccs = {}
for v, r in comp.items():
    sccs.setdefault(r, []).append(v)
print(sorted(sorted(c) for c in sccs.values()))       # [['a', 'b', 'c'], ['d', 'e'], ['f'], ['g']]

dag = sorted({(comp[v], comp[w]) for v in adj for w in adj[v] if comp[v] != comp[w]})
print(dag)                                            # [('a', 'd'), ('d', 'f'), ('g', 'f')]   condensation arcs

Key takeaways

Strongly connected: every vertex reaches every other along directed paths. Weakly connected: connected when directions are ignored.
SCCs are the classes of mutual reachability, and every directed graph splits into them.
The condensation (one vertex per SCC) is always a DAG.
Kosaraju (two DFS passes, one on the reversed graph) and Tarjan (one pass) both run in O(n + m).

Practice

(Beginner) Find the SCCs of the digraph with arcs 1→2, 2→3, 3→1, 3→4, 4→5, 5→6, 6→4, 6→7. Draw its condensation.

(Intermediate) Prove that the condensation of any directed graph is acyclic. Then show that a strongly connected digraph on n ≥ 2 vertices has at least n arcs.

(Interview) A microservice platform records "service X calls service Y" as arcs. Engineers want to find every group of services that are mutually dependent (and so must be deployed together), and an order in which to deploy the groups. Hint: the groups are the SCCs, and a deployment order is a reverse topological order of the condensation. Both come out of a single run of Tarjan's or Kosaraju's algorithm.

Cut Vertices and Bridges

Why. A network is fragile if a single failure can split it. A router whose failure disconnects two offices, or one cable between two data centers, is a single point of failure. Finding these weak spots is the first step in making a network robust, and a clever DFS finds all of them in linear time.

What. In a connected graph:

A cut vertex (articulation point) is a vertex whose removal, together with its incident edges, disconnects the graph. In general, a cut vertex is one whose removal increases the number of components.
A bridge (cut edge) is an edge whose removal increases the number of components.

A graph with at least 3 vertices and no cut vertex is biconnected (2-connected).

Characterizations.

An edge is a bridge if and only if it lies on no cycle. (A cycle gives a detour around the edge, and a detour together with the edge forms a cycle.)
Every edge of a tree is a bridge, and every non-leaf vertex of a tree is a cut vertex (9.1).
If {u, v} is a bridge and deg(u) ≥ 2, then u is a cut vertex.

     a               e
     │ ╲           ╱ │
     │   c ───── d   │          bridges:      {c, d}, {f, g}
     │ ╱           ╲ │          cut vertices: c, d, f
     b               f ───── g

How (Hopcroft–Tarjan). Run a DFS (8.4) and record each vertex's discovery time disc[v]. Define low[v] as the smallest discovery time reachable from v by going down the DFS tree and then following at most one back edge (an edge to an ancestor). Then, for a tree edge from a parent u to a child w:

Condition	Conclusion	Reason
`low[w] > disc[u]`	`{u, w}` is a bridge	Nothing below `w` can reach `u` or above without this edge
`low[w] ≥ disc[u]`, `u` not the root	`u` is a cut vertex	Removing `u` cuts off `w`'s subtree
`u` is the root with `≥ 2` DFS children	`u` is a cut vertex	In an undirected DFS, different subtrees of the root are not joined by any edge

The whole computation is one DFS, so it takes O(n + m) time.

def cut_vertices_and_bridges(adj):
    """Hopcroft–Tarjan low-link DFS for a simple undirected graph."""
    disc, low, cuts, bridges = {}, {}, set(), []
    timer = 0

    def dfs(u, parent):
        nonlocal timer
        disc[u] = low[u] = timer
        timer += 1
        children = 0
        for w in adj[u]:
            if w not in disc:                             # tree edge u -> w
                children += 1
                dfs(w, u)
                low[u] = min(low[u], low[w])
                if low[w] > disc[u]:
                    bridges.append((u, w))                # w's subtree can't get around this edge
                if parent is not None and low[w] >= disc[u]:
                    cuts.add(u)                           # w's subtree can't get around u
            elif w != parent:
                low[u] = min(low[u], disc[w])             # back edge to an ancestor
        if parent is None and children >= 2:
            cuts.add(u)

    for v in adj:                                         # recursion depth ~ n: fine for small graphs
        if v not in disc:
            dfs(v, None)
    return sorted(cuts), bridges

adj = {"a": "bc", "b": "ac", "c": "abd", "d": "cef", "e": "df", "f": "deg", "g": "f"}
print(cut_vertices_and_bridges(adj))                      # (['c', 'd', 'f'], [('f', 'g'), ('c', 'd')])

Key takeaways

Cut vertices and bridges are single points of failure: removing one disconnects the graph.
An edge is a bridge exactly when it lies on no cycle.
One DFS with disc and low values finds all of them in O(n + m): low[w] > disc[u] gives a bridge, and low[w] ≥ disc[u] gives a cut vertex (with a special rule for the root).
A biconnected graph has no cut vertex.

Practice

(Beginner) Find all cut vertices and bridges of the path P₅, the cycle C₅, the star K_{1,4}, and two copies of K₄ sharing one vertex.

(Intermediate) Prove that an edge is a bridge if and only if it lies on no cycle. Then explain why a vertex of degree 1 is never a cut vertex.

(Interview) Given n servers and a list of network links, return every "critical connection", that is, every link whose failure disconnects some servers from others. Your solution must handle 10⁵ servers and links. Hint: this is the bridge-finding DFS. At that size, Python's recursion limit forces an iterative version with an explicit stack. Process a child's low value when the child is popped.

Vertex and Edge Connectivity

Why. Being connected is a yes-or-no property, but network engineers want a number: how many routers or links can fail before the network splits? A network that survives any single failure is good, and one that survives any two failures is better. Vertex and edge connectivity measure exactly this, and Menger's theorem links them to the number of independent routes between nodes.

What.

A vertex cut is a set of vertices whose removal disconnects the graph. The vertex connectivity κ(G) is the size of a smallest vertex cut. For the complete graph, which has no vertex cut, κ(Kₙ) = n − 1 by convention.
An edge cut is a set of edges whose removal disconnects the graph. The edge connectivity λ(G) is the size of a smallest edge cut.
G is k-connected if κ(G) ≥ k, and k-edge-connected if λ(G) ≥ k. A disconnected graph has κ = λ = 0.

Whitney's inequality. For every graph,

  κ(G) ≤ λ(G) ≤ δ(G)

The second inequality is easy: removing all δ edges at a vertex of minimum degree isolates it. The first is proved by removing one well-chosen endpoint of each edge in a minimum edge cut.

Graph	`κ`	`λ`	`δ`
`Kₙ`	`n − 1`	`n − 1`	`n − 1`
`Cₙ`	2	2	2
`Wₙ`	3	3	3
`Qₙ`	`n`	`n`	`n`
`K_{m,n}`, `m ≤ n`	`m`	`m`	`m`
Tree with `n ≥ 3` vertices	1	1	1

The inequalities can all be strict. Take two copies of K₄ and join one vertex a of the first to two vertices w, x of the second:

     b ─── c                 y ─── z
     │ ╲ ╱ │                 │ ╲ ╱ │          κ = 1  (remove a)
     │  ╳  │                 │  ╳  │          λ = 2  (remove {a, w} and {a, x})
     d ─── a ─────────────── w ─── x          δ = 3  (b, c, d, y, z have degree 3)
            ╲                     ╱
             ╰───────────────────╯

(Each K₄ has all six of its edges, and a is joined to both w and x.)

Menger's theorem. For non-adjacent vertices u and v, the minimum number of vertices whose removal separates u from v equals the maximum number of u–v paths that share no vertices except u and v. The edge version says that the minimum number of edges separating u from v equals the maximum number of edge-disjoint u–v paths. So a graph is k-connected exactly when every pair of vertices is joined by k internally disjoint paths. Robustness against failures (a cut) and redundancy of routes (disjoint paths) are the same thing. The edge version is a special case of the max-flow min-cut theorem (8.6), which also gives polynomial-time algorithms for κ and λ.

from itertools import combinations

def connected(vertices, edges):
    vertices = set(vertices)
    if len(vertices) <= 1:
        return True
    adj = {v: set() for v in vertices}
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    start = next(iter(vertices))
    seen, stack = {start}, [start]
    while stack:
        for w in adj[stack.pop()] - seen:
            seen.add(w)
            stack.append(w)
    return seen == vertices

def kappa(V, E):                                   # brute force: try vertex sets by increasing size
    for k in range(len(V) - 1):
        for S in combinations(V, k):
            rest = [v for v in V if v not in S]
            if not connected(rest, [e for e in E if e[0] not in S and e[1] not in S]):
                return k
    return len(V) - 1                              # no vertex cut: complete graph

def lam(V, E):                                     # brute force: try edge sets by increasing size
    for k in range(len(E) + 1):
        for F in combinations(E, k):
            if not connected(V, [e for e in E if e not in F]):
                return k

V = list("abcdwxyz")
E = list(combinations("abcd", 2)) + list(combinations("wxyz", 2)) + [("a", "w"), ("a", "x")]
delta = min(sum(v in e for e in E) for v in V)
print(kappa(V, E), lam(V, E), delta)               # 1 2 3

Q3 = [(u, u ^ b) for u in range(8) for b in (1, 2, 4) if u < u ^ b]
print(kappa(range(8), Q3), lam(range(8), Q3))      # 3 3

Key takeaways

κ(G) is the fewest vertices, and λ(G) the fewest edges, whose removal disconnects G.
Whitney: κ ≤ λ ≤ δ, and each inequality can be strict.
Menger: the size of a minimum separating set equals the maximum number of disjoint paths, in both the vertex and the edge version.
k-connectivity is the standard measure of fault tolerance, and max-flow algorithms (8.6) compute it.

Practice

(Beginner) Compute κ, λ and δ for K_{2,4}, W₆, and the graph made of two triangles sharing one vertex.

(Intermediate) Prove λ(G) ≤ δ(G). Then give a graph with κ(G) = 1 and λ(G) = 5. Hint: glue two large complete graphs at a single vertex.

(Interview) You are designing links between n data centers so that the network stays connected after any 2 link failures, using as few links as possible. What is the lower bound on the number of links, and what topology achieves it? Hint: 3-edge-connected implies δ ≥ 3, so the handshaking lemma gives m ≥ 3n/2. For even n, consider a cycle plus "diameter" chords joining opposite vertices.

8.4 Traversals and Paths

This subchapter covers the two fundamental ways to explore a graph, breadth-first and depth-first search, and then four classic route problems. Two of them, Euler circuits and shortest paths, have fast algorithms. The other two, Hamiltonian cycles and the traveling salesperson problem, have no known efficient algorithm.

Breadth-First Search

Why. To find the fewest hops from one vertex to another (degrees of separation between two users, the minimum number of moves in a puzzle, the fewest router hops), you have to explore the graph in order of distance: first everything one step away, then everything two steps away, and so on. Breadth-first search does exactly that, and it does it in linear time.

What. BFS from a source s visits vertices in layers: layer k is the set of vertices at distance k from s. It keeps a FIFO queue of discovered vertices that have not yet been processed. For each vertex it records

dist[v]: the number of edges on a shortest path from s to v, and
parent[v]: the vertex from which v was discovered. The parent pointers form a BFS tree, and following them back from v gives a shortest path.

Analogy. Drop a stone in a pond. The ripple reaches every point at distance 1 before any point at distance 2. BFS is the ripple, and the queue holds the current wavefront.

How.

Set dist[s] = 0 and put s in the queue.
Remove the vertex u at the front of the queue. For each neighbor w that has not been discovered yet, set dist[w] = dist[u] + 1 and parent[w] = u, and add w to the back of the queue.
Repeat until the queue is empty.

Mark a vertex as discovered when it enters the queue, not when it leaves. Otherwise a vertex can be queued many times.

Every vertex enters the queue at most once, and every adjacency list is scanned once, so BFS runs in O(n + m) time with adjacency lists (O(n²) with a matrix).

Correctness. The queue always holds vertices of at most two consecutive layers, k followed by k + 1. So vertices are removed in non-decreasing order of distance, and each vertex is first discovered from a vertex in the previous layer. Two useful consequences: in an undirected graph, every edge {u, v} satisfies |dist[u] − dist[v]| ≤ 1, and BFS from each vertex of every component tests bipartiteness (8.1).

            s                    layer 0:  s
          ╱   ╲                  layer 1:  a, b
         a     b                 layer 2:  c, d, e
         │ ╲   │                 layer 3:  t
         c   d ─ e
          ╲ ╱                    shortest s–t path: s, a, c, t   (length 3)
           t

from collections import deque

def bfs(adj, s):
    dist, parent = {s: 0}, {s: None}
    queue = deque([s])
    while queue:
        u = queue.popleft()                          # FIFO: closest undiscovered layer first
        for w in adj[u]:
            if w not in dist:                        # mark on enqueue, so each vertex is queued once
                dist[w] = dist[u] + 1
                parent[w] = u
                queue.append(w)
    return dist, parent

def path_to(parent, t):
    path = []
    while t is not None:
        path.append(t)
        t = parent[t]
    return path[::-1]

adj = {"s": "ab", "a": "scd", "b": "se", "c": "at", "d": "aet", "e": "bd", "t": "cd"}
dist, parent = bfs(adj, "s")
print(dist)                                          # {'s': 0, 'a': 1, 'b': 1, 'c': 2, 'd': 2, 'e': 2, 't': 3}
print(path_to(parent, "t"))                          # ['s', 'a', 'c', 't']

Variants. Multi-source BFS starts with several vertices in the queue at distance 0, and computes each vertex's distance to the nearest source (for example, the nearest hospital). 0–1 BFS handles edge weights 0 and 1 with a deque: weight-0 edges go to the front, weight-1 edges to the back. Bidirectional BFS searches from both ends and stops when the two frontiers meet, which explores far fewer vertices in large graphs.

Key takeaways

BFS explores in layers of increasing distance, using a FIFO queue.
In an unweighted graph, it computes shortest-path distances and a shortest-path tree from s in O(n + m).
Mark vertices when they are enqueued. Recover paths by following parent pointers.
It is also the engine for connected components, bipartiteness testing and multi-source distances.

Practice

(Beginner) Run BFS on Q₃ from 000, visiting neighbors in increasing numeric order. List the layers and draw the BFS tree.

(Intermediate) Prove that in an undirected graph, |dist[u] − dist[v]| ≤ 1 for every edge {u, v} after BFS from s. Use it to explain why an edge between two vertices in the same layer means the graph is not bipartite.

(Interview) Word ladder. Given a start word, a target word and a dictionary, find the fewest single-letter changes that turn the start into the target, with every intermediate word in the dictionary. Hint: words are vertices and one-letter changes are edges, but do not build the graph explicitly. Generate the neighbors of each word on the fly (or group words by patterns such as h*t) and run BFS.

Depth-First Search

Why. Some questions are not about distance but about structure. Does this dependency graph have a cycle? In what order can these tasks run? Where are the weak points of this network? Depth-first search answers them. It follows one route as deep as possible before backtracking, and the order in which vertices are entered and left reveals the structure of the graph. It is also the natural way to explore mazes and search spaces (backtracking, 9.4).

What. DFS from s: visit s, then recursively visit each unvisited neighbor in turn. When all of a vertex's neighbors have been visited, backtrack to the vertex that discovered it. The recursion uses the call stack, and an iterative version uses an explicit LIFO stack. Record two timestamps per vertex:

disc[v]: when v is first entered, and
fin[v]: when v is finished, after all its descendants.

Parenthesis theorem. For any two vertices, the intervals [disc, fin] are either nested (one vertex is a descendant of the other) or disjoint. Writing "(v" at disc[v] and "v)" at fin[v] always gives a well-nested expression.

Edge classification. Relative to the DFS forest:

Edge type	From `u` to `w` where …	In undirected graphs?
Tree edge	`w` was discovered through this edge	Yes
Back edge	`w` is an ancestor of `u` (still open)	Yes
Forward edge	`w` is a finished descendant of `u`	No
Cross edge	`w` is finished and in another branch	No

In an undirected graph, every non-tree edge is a back edge. Key facts:

A directed graph has a cycle if and only if DFS finds a back edge. With three colors, white (unvisited), gray (open) and black (finished), a back edge is an edge into a gray vertex.
In a DAG, listing the vertices by decreasing finishing time gives a topological order (2.5). For every arc u → w, w finishes before u.
DFS is the basis of the SCC (8.3) and bridge (8.3) algorithms.

	BFS	DFS
Data structure	Queue (FIFO)	Stack (LIFO) or recursion
Visit order	By distance from the source	Deep first, then backtrack
Shortest paths (unweighted)	Yes	No
Typical uses	Distances, bipartiteness, nearest target	Cycles, topological sort, SCCs, bridges, backtracking
Memory	Up to a whole layer	Up to the longest path explored
Time	`O(n + m)`	`O(n + m)`

WHITE, GRAY, BLACK = 0, 1, 2

def topological_order(adj):
    """Iterative DFS: raise on a back edge, otherwise return vertices by decreasing finishing time."""
    color = {v: WHITE for v in adj}
    finished = []
    for s in adj:
        if color[s] != WHITE:
            continue
        color[s] = GRAY
        stack = [(s, iter(adj[s]))]
        while stack:
            v, it = stack[-1]
            for w in it:
                if color[w] == GRAY:                         # w is open on the stack: back edge
                    raise ValueError(f"cycle through {v} -> {w}")
                if color[w] == WHITE:
                    color[w] = GRAY
                    stack.append((w, iter(adj[w])))
                    break
            else:                                            # all neighbors handled: v finishes
                color[v] = BLACK
                finished.append(v)
                stack.pop()
    return finished[::-1]

dressing = {"undershorts": ["pants", "shoes"], "pants": ["belt", "shoes"], "belt": ["jacket"],
            "shirt": ["belt", "tie"], "tie": ["jacket"], "jacket": [], "socks": ["shoes"], "shoes": []}
print(topological_order(dressing))
# ['socks', 'shirt', 'tie', 'undershorts', 'pants', 'shoes', 'belt', 'jacket']

try:
    topological_order({"a": ["b"], "b": ["c"], "c": ["a"]})
except ValueError as e:
    print(e)                                                 # cycle through c -> a

Key takeaways

DFS goes as deep as possible, then backtracks. It runs in O(n + m) with a stack or with recursion.
Discovery and finishing times are properly nested (parenthesis theorem).
A directed graph is acyclic exactly when DFS finds no back edge (no edge into a gray vertex).
Decreasing finishing time is a topological order of a DAG.
Prefer an explicit stack for deep graphs: recursion depth can reach n.

Practice

(Beginner) Run DFS on the BFS example graph above from s, visiting neighbors in alphabetical order. Give the discovery and finishing times and classify every edge.

(Intermediate) Prove that in a DFS of an undirected graph there are no cross edges, so every edge joins a vertex to one of its ancestors or descendants in the DFS tree.

(Interview) Course schedule. Given n courses and prerequisite pairs, decide whether all courses can be completed and, if so, return a valid order. Compare a DFS-based solution with Kahn's algorithm (2.5). Hint: both run in O(n + m). DFS detects the cycle through a gray vertex, while Kahn's algorithm detects it when some vertices never reach in-degree 0.

Euler Paths and Circuits

Why. In 1736, Euler was asked whether one could walk through the city of Königsberg crossing each of its seven bridges exactly once. His answer founded graph theory. The same question, "traverse every edge exactly once", comes up when planning routes for mail delivery, street sweeping and snow plowing, when drawing figures without lifting the pen, and when reassembling DNA from overlapping fragments.

What. In a graph or multigraph:

An Euler circuit is a closed trail that uses every edge exactly once.
An Euler path (Euler trail) is a trail that uses every edge exactly once, not necessarily closed.

Theorem (Euler, Hierholzer). Let G be a connected multigraph (ignore isolated vertices).

G has an Euler circuit if and only if every vertex has even degree.
G has an Euler path but no Euler circuit if and only if exactly two vertices have odd degree. Every Euler path then starts at one of them and ends at the other.

Proof of necessity. Each time the trail passes through a vertex, it enters on one edge and leaves on another, using two edges. For a closed trail this accounts for every edge at every vertex, so every degree is even. For an open trail, only the start and the end use one unpaired edge each.

Proof of sufficiency (sketch). Start anywhere and walk along unused edges. Because all degrees are even, you can get stuck only at the start vertex, so you have built a closed trail. If some edges are unused, connectedness gives a vertex on the trail with unused edges. Walk a second closed trail from there and splice it in. Repeat until all edges are used. This is Hierholzer's algorithm, and it runs in O(m) time. For two odd vertices, add a temporary edge between them, find a circuit, and remove the edge.

Directed version. A connected digraph has an Euler circuit if and only if deg⁻(v) = deg⁺(v) for every vertex. It has an Euler path from s to t if deg⁺(s) = deg⁻(s) + 1, deg⁻(t) = deg⁺(t) + 1, and all other vertices are balanced.

Königsberg. Four land masses and seven bridges give a multigraph with degrees 5, 3, 3, 3. All four are odd, so there is no Euler path, let alone a circuit.

        north bank C
          ║        ╲
          ║ 2       ╲ 1
          ║          ╲
       island A ── 1 ── D east              degrees: A = 5, B = 3, C = 3, D = 3
          ║          ╱                      four odd vertices: no Euler path
          ║ 2       ╱ 1
          ║        ╱
        south bank B                        (║ = two parallel bridges)

Example: the "house" drawing. The figure below (a square with both diagonals and a roof) has two odd vertices, 1 and 2. So it can be drawn in one stroke, but only by starting at 1 or 2 and finishing at the other.

          5
        ╱   ╲
       4 ─── 3            deg: 1 → 3, 2 → 3, 3 → 4, 4 → 4, 5 → 2
       │ ╲ ╱ │            odd vertices: 1 and 2
       │  ╳  │
       │ ╱ ╲ │
       1 ─── 2

from collections import defaultdict

def euler_path(edges):
    """Hierholzer's algorithm for an undirected multigraph. Returns a vertex sequence or None."""
    adj = defaultdict(list)
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    odd = [v for v in adj if len(adj[v]) % 2 == 1]
    if len(odd) not in (0, 2):
        return None
    start = odd[0] if odd else next(iter(adj))
    used, stack, trail = [False] * len(edges), [start], []
    while stack:
        v = stack[-1]
        while adj[v] and used[adj[v][-1][1]]:
            adj[v].pop()                                  # discard edges already used from the other end
        if adj[v]:
            w, i = adj[v].pop()
            used[i] = True
            stack.append(w)                               # keep walking along unused edges
        else:
            trail.append(stack.pop())                     # stuck: v is final, splice point for sub-tours
    return trail[::-1] if len(trail) == len(edges) + 1 else None   # None if disconnected

house = [(1, 2), (2, 3), (3, 4), (4, 1), (1, 3), (2, 4), (4, 5), (5, 3)]
print(euler_path(house))                                  # [1, 3, 5, 4, 2, 3, 4, 1, 2]

konigsberg = [("A", "B"), ("A", "B"), ("A", "C"), ("A", "C"), ("A", "D"), ("B", "D"), ("C", "D")]
print(euler_path(konigsberg))                             # None

Key takeaways

Euler circuit: every edge exactly once, ending where it started. It exists in a connected graph exactly when every degree is even.
Euler path: exactly zero or two odd-degree vertices, and with two, the path runs between them.
The proof is constructive: Hierholzer's algorithm splices closed trails and runs in O(m).
The directed version replaces "even degree" with "in-degree equals out-degree".

Practice

(Beginner) Which of these have an Euler circuit, and which only an Euler path: K₄, K₅, C₇, W₄, Q₃, Q₄, K_{2,4}, K_{3,3}?

(Intermediate) A road inspector must drive along every street of a town and return to the depot, and the street graph has 2k odd-degree vertices. Explain why at least k streets must be driven twice, and why k repeated streets may not be enough. Hint: repeating a street adds a parallel edge and changes the parity of two degrees. This is the Chinese postman problem.

(Interview) Reconstruct an itinerary. Given a list of airline tickets (from, to) that together form one trip starting at JFK, reconstruct the trip, using every ticket exactly once. Hint: tickets are arcs of a directed multigraph, and the trip is an Euler path. Run Hierholzer's algorithm and output vertices as they are finished, in reverse.

Hamiltonian Paths and Circuits

Why. Euler's problem visits every edge once. The seemingly similar question of visiting every vertex exactly once is far harder. It models scheduling a sequence of jobs with compatibility constraints, a tour that visits every city, and generating every bit string by changing one bit at a time. No simple test like "all degrees even" is known, and the problem is NP-complete (10.3). Recognizing that a problem is Hamiltonian in disguise tells you to stop looking for a fast exact algorithm.

What.

A Hamiltonian path visits every vertex exactly once.
A Hamiltonian cycle (circuit) is a cycle that visits every vertex exactly once and returns to the start.
A graph with a Hamiltonian cycle is Hamiltonian.

The name comes from Hamilton's 1857 "Icosian game": find a cycle through all 20 vertices of a dodecahedron.

	Euler circuit	Hamiltonian cycle
Uses every … exactly once	Edge	Vertex
Simple characterization	Yes: connected and all degrees even	None known
Complexity of deciding	`O(n + m)`	NP-complete
Algorithm	Hierholzer, `O(m)`	Backtracking `O(n!)`, dynamic programming `O(2ⁿ n²)`

Sufficient conditions. These guarantee a Hamiltonian cycle in a simple graph with n ≥ 3 vertices. They are not necessary: Cₙ is Hamiltonian, yet all its degrees are 2.

Dirac (1952): deg(v) ≥ n/2 for every vertex v.
Ore (1960): deg(u) + deg(v) ≥ n for every pair of non-adjacent vertices u, v.

Obstructions. Each of these rules out a Hamiltonian cycle:

a vertex of degree 1, or a cut vertex (8.3);
a set of k vertices whose removal leaves more than k components (a Hamiltonian cycle minus k vertices falls into at most k pieces);
a bipartite graph with parts of different sizes (a Hamiltonian cycle alternates between the parts).

For example, K_{2,3} has no Hamiltonian cycle. The Petersen graph (three-regular, 10 vertices) has a Hamiltonian path but no Hamiltonian cycle.

Gray codes. Qₙ is Hamiltonian for every n ≥ 2. The reflected Gray code builds the cycle by induction: list the cycle for Qₙ₋₁ with 0 prepended, then the same list in reverse with 1 prepended. Consecutive codes differ in one bit, so a rotary encoder that reads a Gray code can never be off by more than one position.

How. For small n, the Held–Karp dynamic program decides the question in O(2ⁿ n²) time instead of O(n!). Let ends[S] be the set of vertices v such that some path visits exactly the vertices of S and ends at v. Each such path extends to any neighbor of v outside S.

def gray_code(n):
    if n == 0:
        return [""]
    prev = gray_code(n - 1)
    return ["0" + c for c in prev] + ["1" + c for c in reversed(prev)]   # reflect

codes = gray_code(3)
print(codes)                     # ['000', '001', '011', '010', '110', '111', '101', '100']
print(all(sum(a != b for a, b in zip(codes[i], codes[(i + 1) % 8])) == 1 for i in range(8)))   # True

def hamiltonian(n, edges, cycle=False):
    """Held–Karp style DP over vertex subsets, encoded as bitmasks."""
    nbr = [0] * n
    for u, v in edges:
        nbr[u] |= 1 << v
        nbr[v] |= 1 << u
    ends = [0] * (1 << n)                        # ends[S]: bitset of possible last vertices
    for v in ([0] if cycle else range(n)):       # a cycle can be assumed to start at vertex 0
        ends[1 << v] = 1 << v
    for S in range(1 << n):
        for v in range(n):
            if ends[S] >> v & 1:
                ext = nbr[v] & ~S                # neighbors of v not yet visited
                while ext:
                    w = ext & -ext               # lowest set bit
                    ends[S | w] |= w
                    ext ^= w
    full = ends[(1 << n) - 1]
    return bool(full & nbr[0]) if cycle else full != 0     # a cycle must close back to vertex 0

petersen = ([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
            + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])
print(hamiltonian(10, petersen), hamiltonian(10, petersen, cycle=True))   # True False

K23 = [(a, b) for a in (0, 1) for b in (2, 3, 4)]
print(hamiltonian(5, K23), hamiltonian(5, K23, cycle=True))               # True False

Key takeaways

A Hamiltonian path or cycle visits every vertex exactly once.
Unlike the Euler case, no simple characterization is known, and deciding is NP-complete.
Dirac's and Ore's conditions are sufficient. Cut vertices, leaves and unbalanced bipartite graphs are obstructions.
Qₙ is Hamiltonian (Gray codes). The Petersen graph is not.
The Held–Karp dynamic program decides it in O(2ⁿ n²), which is practical up to about n = 25.

Practice

(Beginner) Find a Hamiltonian cycle in K_{3,3}, in W₅, and in Q₃ (using the Gray code above). Explain why K_{3,4} has none.

(Intermediate) Prove by induction that the reflected Gray code of order n is a Hamiltonian cycle of Qₙ for n ≥ 2. Hint: the two halves are paths by the induction hypothesis. Check the two "seams" where the halves meet, including the wrap-around.

(Interview) A puzzle asks whether a knight can visit every square of a 5 × 5 board exactly once. How would you solve it, and how would your approach change for 8 × 8? Hint: this is a Hamiltonian path in the knight's-move graph. Bitmask DP needs 2²⁵ states, which is borderline, while backtracking with Warnsdorff's heuristic (always move to the square with the fewest onward moves) finds 8 × 8 tours almost instantly.

Dijkstra's Shortest Path Algorithm

Why. In a road network, the route with the fewest road segments is rarely the fastest one. Edges have lengths, travel times, or costs, and we want the path of minimum total weight. Dijkstra's algorithm (1959) solves this for non-negative weights. It runs inside navigation apps, link-state routing protocols such as OSPF, and as a building block in many other algorithms.

What. A weighted graph has a weight w(u, v) ≥ 0 on each edge. The weight of a path is the sum of its edge weights, and d(s, v) is the minimum weight of an s–v path. The key structural fact is optimal substructure: every part of a shortest path is itself a shortest path. If a shortcut existed for some part, it would shorten the whole path.

How. Dijkstra's algorithm keeps a tentative distance dist[v] (initially ∞, and 0 for s) and a set of finalized vertices. It repeats:

Pick the non-finalized vertex u with the smallest dist[u], and finalize it.
Relax each edge (u, w): if dist[u] + w(u, w) < dist[w], lower dist[w] and set parent[w] = u.

Why it is correct. Suppose u is the next vertex to be finalized, and consider any s–u path. It leaves the finalized set at some edge (x, y). The path's weight is at least d(s, x) + w(x, y) ≥ dist[y] ≥ dist[u], because weights are non-negative and u was chosen with the smallest tentative distance. So no path beats dist[u], and dist[u] = d(s, u). This argument uses non-negative weights, and the algorithm can fail without them.

Analogy. Picture water flowing out from s through pipes whose lengths are the edge weights. The water reaches the vertices in order of distance, and Dijkstra's algorithm simulates the moments of arrival. A negative edge would be a pipe that delivers water before it was sent.

Example.

     A ──4── B ──5── D ──6── F
      ╲     ╱         ╲     ╱
       2   1           2   3
        ╲ ╱             ╲ ╱
         C ──────10────── E

Step	Finalize	`B`	`C`	`D`	`E`	`F`
0		∞	∞	∞	∞	∞
1	`A`	4	2	∞	∞	∞
2	`C`	3	2	∞	12	∞
3	`B`	3	2	8	12	∞
4	`D`	3	2	8	10	14
5	`E`	3	2	8	10	13
6	`F`	3	2	8	10	13

The bold entry in each row is the next vertex to be finalized. The shortest A–F path is A, C, B, D, E, F with weight 2 + 1 + 5 + 2 + 3 = 13. It has five edges, while the path with the fewest edges, A, B, D, F, weighs 15.

Complexity.

Priority queue	Time	Best for
Unsorted array	`O(n²)`	Dense graphs
Binary heap	`O((n + m) log n)`	Sparse graphs, the usual choice
Fibonacci heap	`O(m + n log n)`	Theoretical bound

Related algorithms. With unit weights, BFS is enough. With negative edges but no negative cycles, use Bellman–Ford, O(nm). For all pairs, use Floyd–Warshall, O(n³). For a single target with a good distance estimate (such as straight-line distance on a map), A* explores far fewer vertices.

import heapq

def dijkstra(adj, s):
    dist, parent = {s: 0}, {s: None}
    heap, done = [(0, s)], set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in done:
            continue                                   # stale entry: u was finalized with a smaller key
        done.add(u)
        for w, weight in adj[u]:
            nd = d + weight
            if nd < dist.get(w, float("inf")):         # relax the edge u -> w
                dist[w], parent[w] = nd, u
                heapq.heappush(heap, (nd, w))          # lazy insert instead of decrease-key
    return dist, parent

def undirected(edges):
    adj = {}
    for u, v, w in edges:
        adj.setdefault(u, []).append((v, w))
        adj.setdefault(v, []).append((u, w))
    return adj

roads = undirected([("A", "B", 4), ("B", "D", 5), ("D", "F", 6), ("A", "C", 2),
                    ("C", "B", 1), ("D", "E", 2), ("E", "F", 3), ("C", "E", 10)])
dist, parent = dijkstra(roads, "A")
print(dict(sorted(dist.items())))                      # {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10, 'F': 13}
path, v = [], "F"
while v:
    path.append(v)
    v = parent[v]
print(path[::-1])                                      # ['A', 'C', 'B', 'D', 'E', 'F']

# A negative edge breaks the invariant: a is finalized at 2 before the cheaper route through b is seen.
neg = {"s": [("a", 2), ("b", 5)], "a": [("t", 1)], "b": [("a", -4)], "t": []}
print(dijkstra(neg, "s")[0]["t"])                      # 3, but the true distance s -> b -> a -> t is 2

Key takeaways

Dijkstra's algorithm finds shortest paths from one source when all weights are non-negative.
It finalizes vertices in order of distance and relaxes the edges out of each finalized vertex.
With a binary heap it runs in O((n + m) log n).
Negative weights break it. Use Bellman–Ford instead, or BFS when all weights are equal.

Practice

(Beginner) Run Dijkstra's algorithm on the example graph from F. Fill in the table and give the shortest path to A.

(Intermediate) Adding the same constant to every edge weight does not "fix" negative weights. Give a small graph where it changes which path is shortest. Hint: the constant is added once per edge, so it penalizes paths with many edges.

(Interview) A flight search must find the cheapest route from src to dst with at most k stops. Why does plain Dijkstra fail, and what would you do? Hint: the state must include the number of edges used, (vertex, stops). Either run Dijkstra on that expanded state space or run k + 1 rounds of Bellman–Ford relaxation.

Traveling Salesperson Problem

Why. A delivery van must visit 40 addresses and return to the depot. A drilling machine must make 10,000 holes in a circuit board. A telescope must observe a list of stars. In each case, the order of visits determines the cost, and the goal is the cheapest closed tour. This is the traveling salesperson problem (TSP), the most studied problem in combinatorial optimization and the standard example of an NP-hard problem.

What. Given a complete graph with a weight (distance) w(u, v) on every edge, find a Hamiltonian cycle of minimum total weight. With n cities and symmetric distances, there are (n − 1)!/2 distinct tours: fix the starting city, order the rest, and identify each tour with its reverse.

`n`	Distinct tours `(n − 1)!/2`
5	12
10	181,440
20	about `6.1 · 10¹⁶`
50	about `3 · 10⁶²`

The decision version ("is there a tour of weight at most B?") is NP-complete (10.3), because the Hamiltonian cycle problem reduces to it: give existing edges weight 1, missing edges weight 2, and ask for a tour of weight n.

How. Exact methods:

Brute force over all tours, O(n!): hopeless beyond about 12 cities.
Held–Karp dynamic programming, O(n² 2ⁿ): let C(S, v) be the cheapest path that starts at city 0, visits exactly the cities in S, and ends at v ∈ S. Then C(S, v) = min over u ∈ S − {v} of C(S − {v}, u) + w(u, v). It is practical up to about 25 cities.
Branch and bound and integer linear programming with cutting planes. The Concorde solver has solved instances with tens of thousands of cities to proven optimality.

Approximate methods:

Nearest neighbor: always go to the closest unvisited city. It is fast, but it can be far from optimal.
Local search, such as 2-opt: repeatedly reverse a segment of the tour if that removes two crossing edges and shortens it. It is very effective in practice.
Guaranteed approximations for metric TSP, where distances satisfy the triangle inequality w(u, v) ≤ w(u, x) + w(x, v). Walking around a minimum spanning tree (9.4) and skipping repeated cities gives a tour at most twice the optimum. Christofides' algorithm gets within a factor of 1.5. Without the triangle inequality, no constant-factor approximation exists unless P = NP.

from itertools import combinations

D = [[0, 2, 9, 10, 7],                      # symmetric distance matrix for 5 cities
     [2, 0, 6, 4, 3],
     [9, 6, 0, 8, 5],
     [10, 4, 8, 0, 6],
     [7, 3, 5, 6, 0]]
n = len(D)

def held_karp(D):
    """C[(S, v)]: cheapest path from city 0 through exactly the cities in bitmask S, ending at v."""
    n = len(D)
    C = {(1 << v, v): (D[0][v], 0) for v in range(1, n)}            # (cost, previous city)
    for size in range(2, n):
        for subset in combinations(range(1, n), size):
            S = sum(1 << v for v in subset)
            for v in subset:
                prev = S & ~(1 << v)
                C[(S, v)] = min((C[(prev, u)][0] + D[u][v], u) for u in subset if u != v)
    full = (1 << n) - 2                                              # every city except 0
    cost, last = min((C[(full, v)][0] + D[v][0], v) for v in range(1, n))
    tour, S = [], full
    while last:                                                      # follow the stored predecessors back
        tour.append(last)
        S, last = S & ~(1 << last), C[(S, last)][1]
    return cost, [0] + tour[::-1]

def nearest_neighbor(D, start=0):
    tour, left = [start], set(range(len(D))) - {start}
    while left:
        nxt = min(left, key=lambda j: D[tour[-1]][j])                # greedy: closest unvisited city
        tour.append(nxt)
        left.remove(nxt)
    return sum(D[tour[i]][tour[(i + 1) % len(tour)]] for i in range(len(tour))), tour

print(held_karp(D))                                                  # (26, [0, 4, 2, 3, 1])
print(nearest_neighbor(D))                                           # (28, [0, 1, 4, 2, 3])

The optimal tour 0, 4, 2, 3, 1 is the reverse of 0, 1, 3, 2, 4, which is the same cycle. Nearest neighbor greedily takes the short edge 1–4 early and pays for it with the long edge 3–0 at the end.

Key takeaways

TSP asks for a minimum-weight Hamiltonian cycle in a complete weighted graph. It has (n − 1)!/2 tours.
It is NP-hard. Held–Karp solves it exactly in O(n² 2ⁿ), and practical solvers use branch and bound or integer programming.
Heuristics such as nearest neighbor and 2-opt give good tours quickly, without a guarantee.
With the triangle inequality, MST-based methods give guaranteed approximations (factor 2, or 1.5 for Christofides).

Practice

(Beginner) How many distinct tours are there on 6 cities with symmetric distances? Enumerate them for 4 cities A, B, C, D and find the cheapest when w(A,B) = 1, w(A,C) = 3, w(A,D) = 4, w(B,C) = 2, w(B,D) = 5, w(C,D) = 1.

(Intermediate) Prove that the weight of a minimum spanning tree is at most the weight of an optimal tour. Then explain why walking around the tree and skipping repeated cities gives a tour of at most twice the optimum when the triangle inequality holds. Hint: deleting one edge from a tour leaves a spanning tree.

(Interview) A courier app must reorder 150 stops in under one second each time a new order arrives. What would you implement, and how would you measure its quality without knowing the optimum? Hint: start with a fast construction (nearest neighbor or insertion), improve it with 2-opt for the time available, and reuse the previous tour when a stop is added. Compare against a lower bound such as the MST weight.

8.5 Planarity and Coloring

This subchapter is about two classic structural questions. Can a graph be drawn in the plane without crossing edges? And how few colors are needed so that adjacent vertices (or edges) get different colors? The two questions meet in the Four Color Theorem.

Planar Graphs

Why. On a single-layer circuit board, wires cannot cross. A subway map is easier to read with fewer crossings, and a map of countries is a drawing with no crossings at all. All of these lead to the question of which graphs can be drawn in the plane so that edges meet only at their endpoints. The answer also matters for algorithms, because many problems that are hard in general become easier on planar graphs.

What. A graph is planar if it can be drawn in the plane with no edges crossing. Such a drawing is a plane graph (or a planar embedding). Planarity is a property of the graph, not of a particular drawing: a planar graph can also be drawn badly, with crossings.

K₄ is planar, even though its most obvious drawing has a crossing:

   drawn with a crossing        drawn without crossings
                                          a
      a ──────── b                      ╱ │ ╲
      │ ╲      ╱ │                     ╱  │  ╲
      │   ╲  ╱   │                    ╱   d   ╲
      │    ╱╲    │                   ╱  ╱   ╲  ╲
      │  ╱    ╲  │                  ╱ ╱       ╲ ╲
      c ──────── d                 b ─────────── c

A plane graph divides the plane into faces (regions). Exactly one face, the outer face, is unbounded. The planar drawing of K₄ above has 4 faces: the three triangles around d and the outer face.

The degree of a face is the number of edge-sides on its boundary, walking around it. An edge that separates two faces counts once for each. A bridge has the same face on both sides, so it counts twice for that face. Every edge has two sides, so

  Σ_{faces F} deg(F) = 2m

which is the handshaking lemma for faces.

Examples.

Planar	Not planar
All trees, all cycles `Cₙ`, all wheels `Wₙ`	`K₅`
`K₄`, `K_{2,n}` for every `n`	`K_{3,3}` (the "three utilities" puzzle)
`Q₃` (the cube) and the graphs of all convex polyhedra	`Kₙ` for `n ≥ 5`, `K_{m,n}` for `m, n ≥ 3`
Road networks without bridges and tunnels, maps	The Petersen graph

The three utilities puzzle asks you to connect three houses to three utilities (water, gas, electricity) without any lines crossing. That is a planar drawing of K_{3,3}, which does not exist (next topic).

Fáry's theorem. Every planar graph has a planar drawing in which every edge is a straight segment. So planarity can be checked on straight-line drawings, and crossings in a straight-line drawing can be counted with simple geometry:

def orient(p, q, r):                                   # sign of the turn p -> q -> r
    return (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])

def crossings(pos, edges):
    """Count pairs of straight edges that cross (edges sharing an endpoint never count)."""
    count = 0
    for i, (a, b) in enumerate(edges):
        for c, d in edges[i + 1:]:
            if {a, b} & {c, d}:
                continue
            P, Q, R, S = pos[a], pos[b], pos[c], pos[d]
            if orient(P, Q, R) * orient(P, Q, S) < 0 and orient(R, S, P) * orient(R, S, Q) < 0:
                count += 1                             # each segment separates the other's endpoints
    return count

K4 = [("a", "b"), ("a", "c"), ("a", "d"), ("b", "c"), ("b", "d"), ("c", "d")]
square   = {"a": (0, 2), "b": (2, 2), "c": (0, 0), "d": (2, 0)}
triangle = {"a": (2, 4), "b": (0, 0), "c": (4, 0), "d": (2, 1)}
print(crossings(square, K4), crossings(triangle, K4))   # 1 0

Testing whether some drawing has no crossings is harder, but linear-time planarity testing algorithms exist (Hopcroft–Tarjan 1974, Boyer–Myrvold 2004). They either produce a planar embedding or point to a forbidden subgraph (Kuratowski's theorem).

Key takeaways

A graph is planar if some drawing of it has no crossing edges. One bad drawing proves nothing.
A plane drawing splits the plane into faces, and the face degrees add up to 2m.
K₄, trees, cycles, wheels and Q₃ are planar. K₅ and K_{3,3} are not.
Every planar graph has a straight-line planar drawing (Fáry), and planarity can be tested in linear time.

Practice

(Beginner) Draw Q₃ and W₅ without crossings, and count the faces of each drawing.

(Intermediate) Show that K_{2,n} is planar for every n, and that K₅ minus any one edge is planar, by giving explicit drawings.

(Interview) A diagram tool lays out a dependency graph and the output is full of crossings. The user asks whether a crossing-free layout exists. How would you answer, and what would you show the user when it does not exist? Hint: run a linear-time planarity test. When it fails, it can return a subdivision of K₅ or K_{3,3} as a certificate. Minimizing the number of crossings, as opposed to deciding whether it can be zero, is NP-hard.

Euler's Formula

Why. Planarity seems to be about geometry, but a simple counting law holds for every planar drawing: vertices minus edges plus faces is always 2. The formula turns geometric questions into arithmetic. It proves that K₅ and K_{3,3} are not planar, it shows that planar graphs are sparse, and it guarantees a low-degree vertex, which is the key step in proving the color theorems below.

What. For a connected plane graph with n vertices, m edges and f faces,

  n − m + f = 2

Proof by induction on m (3.2). A connected graph with n vertices has at least n − 1 edges (8.3).

Basis m = n − 1: the graph is a tree (9.1). A tree has no cycles, so it does not enclose any region, and f = 1. Then n − (n − 1) + 1 = 2.
Step m ≥ n: the graph is not a tree, so it has a cycle. Remove an edge e of the cycle. The graph stays connected, and the two faces on either side of e (different faces, because a cycle separates the plane into an inside and an outside) merge into one. So n is unchanged and m and f both drop by 1. By the induction hypothesis, n − (m − 1) + (f − 1) = 2, which equals n − m + f.

For a plane graph with c connected components, the formula becomes n − m + f = 1 + c. For a convex polyhedron, it is Euler's polyhedron formula V − E + F = 2:

Solid	`V`	`E`	`F`	`V − E + F`
Tetrahedron	4	6	4	2
Cube	8	12	6	2
Octahedron	6	12	8	2
Dodecahedron	20	30	12	2
Icosahedron	12	30	20	2

Corollaries. Let G be a simple planar graph with n ≥ 3 vertices.

m ≤ 3n − 6. For a connected G, every face has degree at least 3 (there are no loops or multiple edges, and a graph with n ≥ 3 is not a single edge). So 2m = Σ deg(F) ≥ 3f. Substituting f ≤ 2m/3 into Euler's formula gives 2 = n − m + f ≤ n − m/3. If G is disconnected, add edges until it is connected, which keeps it planar.
m ≤ 2n − 4 if G has no triangles (in particular, if G is bipartite). Now every face has degree at least 4, so 2m ≥ 4f. More generally, if the shortest cycle has length g, then m ≤ g(n − 2)/(g − 2).
G has a vertex of degree at most 5. Otherwise 2m = Σ deg(v) ≥ 6n, contradicting m ≤ 3n − 6.

Applications.

K₅: n = 5, m = 10 > 3 · 5 − 6 = 9. Not planar.
K_{3,3}: n = 6, m = 9 ≤ 12, so corollary 1 says nothing. But K_{3,3} is bipartite, and m = 9 > 2 · 6 − 4 = 8. Not planar.
The Petersen graph has n = 10, m = 15 and girth 5, so a planar drawing would need m ≤ 5 · 8/3 ≈ 13.3. Not planar.

These bounds are necessary conditions only. A graph can satisfy m ≤ 3n − 6 and still not be planar: K₅ plus 5 isolated vertices has n = 10 and m = 10 ≤ 24.

platonic = {"tetrahedron": (4, 6, 4), "cube": (8, 12, 6), "octahedron": (6, 12, 8),
            "dodecahedron": (20, 30, 12), "icosahedron": (12, 30, 20)}
print({name: V - E + F for name, (V, E, F) in platonic.items()})
# {'tetrahedron': 2, 'cube': 2, 'octahedron': 2, 'dodecahedron': 2, 'icosahedron': 2}

def edge_bound(n, girth=3):
    """Largest m allowed by Euler's formula for a simple planar graph with n >= 3 vertices."""
    return girth * (n - 2) / (girth - 2)

for name, n, m, g in [("K5", 5, 10, 3), ("K3,3", 6, 9, 4), ("Petersen", 10, 15, 5), ("Q3", 8, 12, 4)]:
    verdict = "not planar" if m > edge_bound(n, g) else "no conclusion"
    print(f"{name:9} m = {m:2}  bound = {edge_bound(n, g):5.2f}  {verdict}")
# K5        m = 10  bound =  9.00  not planar
# K3,3      m =  9  bound =  8.00  not planar
# Petersen  m = 15  bound = 13.33  not planar
# Q3        m = 12  bound = 12.00  no conclusion

Q₃ meets the bound with equality, and it is in fact planar: its planar drawing is the cube, all of whose faces are 4-cycles.

Key takeaways

For a connected plane graph, n − m + f = 2. Every planar drawing of the graph has the same number of faces.
Simple planar graphs are sparse: m ≤ 3n − 6, and m ≤ 2n − 4 without triangles.
K₅ and K_{3,3} violate these bounds, so they are not planar.
Every simple planar graph has a vertex of degree at most 5.
The bounds can prove non-planarity, but never planarity.

Practice

(Beginner) A connected planar graph has 10 vertices, each of degree 3. How many faces does every planar drawing of it have?

(Intermediate) Prove that a connected simple planar graph in which every face is a triangle has exactly 3n − 6 edges. Then show that the average degree of any simple planar graph is less than 6.

(Interview) Prove, using only Euler's formula, that there are exactly five Platonic solids (convex polyhedra in which every face is a regular p-gon and every vertex has degree q). Hint: pF = 2E = qV. Substitute into V − E + F = 2 to get 1/p + 1/q = 1/2 + 1/E > 1/2, and list the integer solutions with p, q ≥ 3.

Kuratowski's Theorem

Why. Euler's formula shows that some graphs are not planar, but it cannot prove that a graph is planar, and some non-planar graphs satisfy all its bounds. Kuratowski's theorem (1930) gives a complete answer: K₅ and K_{3,3} are essentially the only obstacles. Every non-planar graph contains one of them in a stretched-out form, and that copy is a short, checkable proof of non-planarity.

What. An elementary subdivision replaces an edge {u, v} with a path u, w, v through a new vertex w of degree 2. A subdivision of H is any graph obtained from H by repeated elementary subdivisions. In other words, it is H with some edges replaced by paths. Two graphs are homeomorphic if they have subdivisions that are isomorphic. Subdividing never affects planarity, because adding a vertex in the middle of an edge does not change the drawing.

Kuratowski's theorem. A graph is planar if and only if it contains no subgraph that is a subdivision of K₅ or of K_{3,3}.

One direction is easy: a subdivision of a non-planar graph is non-planar, and a subgraph of a planar graph is planar. The other direction is the deep part.

Wagner's theorem (1937) is an equivalent version in terms of minors. A minor of G is any graph obtained from a subgraph of G by contracting edges, which means merging the two endpoints of an edge into one vertex. A graph is planar if and only if it has neither K₅ nor K_{3,3} as a minor. The Robertson–Seymour theorem generalizes this idea: every family of graphs that is closed under taking minors is characterized by a finite list of forbidden minors.

   K₃,₃                                 a subdivision of K₃,₃

   h₁      h₂      h₃                   h₁      h₂      h₃
   │ ╲   ╱ │ ╲   ╱ │                    │ ╲   ╱ │ ╲   ╱ │
   │   ╳   │   ╳   │                    s   ╳   │   ╳   t
   │ ╱   ╲ │ ╱   ╲ │                    │ ╱   ╲ │ ╱   ╲ │
   u₁      u₂      u₃                   u₁      u₂      u₃

   plus the two long edges h₁u₃ and h₃u₁ (not drawn) in both graphs.
   On the right, the edges h₁u₁ and h₃u₃ are replaced by the paths h₁, s, u₁ and h₃, t, u₃.

The Petersen graph is not planar. Delete one outer vertex. Three vertices of the remaining graph now have degree 2. Smooth them out (undo the subdivisions), and the result is K_{3,3}. So the Petersen graph contains a subdivision of K_{3,3}. It contains no subdivision of K₅, because it has no vertex of degree 4, but it does have K₅ as a minor: contract the five spokes.

def smooth(adj):
    """Undo subdivisions: replace each degree-2 vertex u - v - w by a direct edge u - w."""
    adj = {v: set(ns) for v, ns in adj.items()}
    changed = True
    while changed:
        changed = False
        for v in list(adj):
            if len(adj[v]) == 2:
                a, b = adj[v]
                if b not in adj[a]:                       # do not create a parallel edge
                    adj[a] -= {v}; adj[b] -= {v}
                    adj[a].add(b); adj[b].add(a)
                    del adj[v]
                    changed = True
    return adj

def is_K33(adj):
    if len(adj) != 6 or any(len(ns) != 3 for ns in adj.values()):
        return False
    v = next(iter(adj))
    side = adj[v]                                         # in K3,3, v's neighbors form the other side
    other = set(adj) - side
    return all(adj[x] == other for x in side) and all(adj[y] == side for y in other)

edges = ([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
         + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])  # Petersen: outer 5-cycle, spokes, inner pentagram
petersen = {v: set() for v in range(10)}
for u, v in edges:
    petersen[u].add(v); petersen[v].add(u)

minus0 = {v: ns - {0} for v, ns in petersen.items() if v != 0}       # delete vertex 0
print(sorted(v for v, ns in minus0.items() if len(ns) == 2))      # [1, 4, 5]   the subdivision vertices
core = smooth(minus0)
print(sorted(core), is_K33(core))                                 # [2, 3, 6, 7, 8, 9] True

Key takeaways

A subdivision replaces edges by paths. It does not change planarity.
Kuratowski: a graph is planar exactly when it contains no subdivision of K₅ or K_{3,3}.
Wagner: equivalently, a graph is planar exactly when it has no K₅ or K_{3,3} minor.
A Kuratowski subgraph is a certificate of non-planarity, and linear-time planarity tests can produce one.

Practice

(Beginner) Show that K_{3,3} minus one edge is planar by drawing it. Then explain why the graph obtained from K₅ by subdividing every edge once is still not planar, even though it is bipartite.

(Intermediate) Show that Q₄ is not planar, first with Euler's formula, then by finding a subdivision of K_{3,3} in it. Hint: Q₄ is bipartite with n = 16 and m = 32.

(Interview) Explain why the brute-force strategy "try every subset of edges and test whether it is a subdivision of K₅ or K_{3,3}" is impractical, and how the linear-time planarity algorithms avoid it. Hint: there are 2ᵐ subsets. Efficient algorithms build an embedding incrementally (for example, adding vertices in DFS order) and extract a Kuratowski subgraph only at the point where the embedding gets stuck.

Graph Coloring

Why. Suppose some exams cannot be held at the same time, because a student takes both. How many time slots are needed? Radio towers that are close together need different frequencies, and variables that are live at the same moment need different CPU registers. All of these are the same problem: assign a "color" (slot, frequency, register) to each vertex of a conflict graph so that conflicting vertices get different colors, using as few colors as possible.

What. A (proper) vertex coloring with k colors is a function c : V → {1, …, k} with c(u) ≠ c(v) for every edge {u, v}. A graph with such a coloring is k-colorable. Each color class c⁻¹(i) is an independent set, so a k-coloring is the same as a partition of V into k independent sets.

How: greedy coloring. Take the vertices in some order and give each one the smallest color not used by its already-colored neighbors.

A vertex has at most Δ neighbors, so some color among 1, …, Δ + 1 is always free. Greedy coloring therefore uses at most Δ + 1 colors, and it runs in O(n + m) time.
The result depends heavily on the order. For every graph, some order makes greedy coloring optimal, but finding it is as hard as the coloring problem itself. Welsh–Powell (largest degree first) and DSatur (most distinct neighbor colors first) are good heuristics.

Example: exam scheduling. Four students take these courses: {Math, Physics, CS}, {CS, Chem}, {Chem, Bio} and {Bio, Art, Math}. Two courses conflict when a student takes both.

        Physics
        ╱     ╲
     Math ───── CS              Math, Physics, CS form a triangle,
      │  ╲        ╲             so at least 3 time slots are needed
      │   ╲        Chem
      │    ╲      ╱
     Art ── Bio ─╯

Bad orders. The crown graph is K_{n,n} with a perfect matching removed: aᵢ is adjacent to bⱼ exactly when i ≠ j. It is bipartite, so 2 colors suffice. But in the order a₁, b₁, a₂, b₂, …, greedy coloring gives aᵢ and bᵢ color i, using n colors.

def greedy_coloring(adj, order):
    color = {}
    for v in order:
        used = {color[w] for w in adj[v] if w in color}
        color[v] = next(c for c in range(len(adj)) if c not in used)   # smallest free color
    return color

students = [{"Math", "Physics", "CS"}, {"CS", "Chem"}, {"Chem", "Bio"}, {"Bio", "Art", "Math"}]
conflicts = {c: set() for s in students for c in s}
for s in students:
    for c in s:
        conflicts[c] |= s - {c}                                        # courses sharing a student

welsh_powell = sorted(conflicts, key=lambda c: (-len(conflicts[c]), c))   # largest degree first
slots = greedy_coloring(conflicts, welsh_powell)
print(welsh_powell)                    # ['Math', 'Bio', 'CS', 'Art', 'Chem', 'Physics']
print(slots)                           # {'Math': 0, 'Bio': 1, 'CS': 1, 'Art': 2, 'Chem': 0, 'Physics': 2}

n = 4                                  # crown graph on a1..a4, b1..b4
crown = {f"{s}{i}": {f"{t}{j}" for j in range(1, n + 1) if j != i}
         for s, t in [("a", "b"), ("b", "a")] for i in range(1, n + 1)}
interleaved = [f"{s}{i}" for i in range(1, n + 1) for s in "ab"]
by_side = sorted(crown)                                            # a1..a4, then b1..b4
print(len(set(greedy_coloring(crown, interleaved).values())))      # 4
print(len(set(greedy_coloring(crown, by_side).values())))          # 2

Key takeaways

A proper coloring gives adjacent vertices different colors, and each color class is an independent set.
Scheduling, frequency assignment and register allocation are coloring problems on a conflict graph.
Greedy coloring uses at most Δ + 1 colors, but the result depends on the vertex order.
Welsh–Powell and DSatur choose good orders, but no fast method is optimal on every graph.

Practice

(Beginner) Color C₆, C₇, W₆ and Q₃ with as few colors as you can, and argue that you cannot use fewer.

(Intermediate) Prove that greedy coloring never uses more than Δ + 1 colors. Then prove that for every graph there is an order in which greedy coloring uses exactly χ(G) colors (next topic). Hint: take an optimal coloring and list its color classes one after another.

(Interview) In a compiler, two variables interfere if they are live at the same time, and each must get one of k registers. How do you model this, and what do you do when the graph needs more than k colors? Hint: this is coloring of the interference graph. Chaitin-style allocators repeatedly remove vertices of degree less than k (they can always be colored later), and "spill" a variable to memory when no such vertex remains.

Chromatic Number

Why. For every coloring problem, the natural question is: what is the fewest number of colors possible? This number, the chromatic number, measures how "conflicted" a graph is. Knowing its value, or at least good bounds, tells you whether a schedule with k slots exists. It is also one of the central hard problems of computer science.

What. The chromatic number χ(G) is the smallest k for which G is k-colorable.

Graph	`χ`	Reason
No edges	1
Bipartite with at least one edge, including trees, even cycles and `Qₙ`	2	2-colorable (8.1)
`Cₙ`, `n` odd	3	Odd cycles are not bipartite
`Kₙ`	`n`	All vertices are pairwise adjacent
`Wₙ`, `n` even	3	The rim takes 2 colors, the hub a third
`Wₙ`, `n` odd	4	The odd rim takes 3 colors, the hub a fourth
Petersen graph	3	Contains a 5-cycle, and a 3-coloring exists
Planar graphs	`≤ 4`	Four Color Theorem (next topic)

Bounds. Let ω(G) be the size of the largest clique and α(G) the size of the largest independent set.

χ(G) ≥ ω(G): a clique needs all different colors.
χ(G) ≥ n / α(G): each color class is an independent set, so it has at most α vertices.
χ(G) ≤ Δ(G) + 1: greedy coloring.
Brooks' theorem: χ(G) ≤ Δ(G) for a connected graph, unless G is a complete graph or an odd cycle.

The clique bound can be far from the truth. Mycielski's construction produces triangle-free graphs (ω = 2) with any chromatic number you want. A large chromatic number does not require a large clique.

Complexity. Deciding χ(G) ≤ 2 is easy (BFS, 8.1). Deciding χ(G) ≤ 3 is NP-complete, even for planar graphs with maximum degree 4. Approximating χ within a factor of n^{1−ε} is also NP-hard. In practice, χ is computed by backtracking with good pruning, or by SAT and integer-programming solvers.

Chromatic polynomial. P(G, k) is the number of proper colorings of G with at most k colors (colorings that use colors from a set of k, not necessarily all of them). Then χ(G) is the smallest positive integer k with P(G, k) > 0.

P(Kₙ, k) = k(k − 1)(k − 2) ⋯ (k − n + 1), a falling factorial (5.2).
P(T, k) = k(k − 1)ⁿ⁻¹ for every tree T on n vertices: color the root, then each child avoids its parent's color.
P(Cₙ, k) = (k − 1)ⁿ + (−1)ⁿ(k − 1).
Deletion–contraction: P(G, k) = P(G − e, k) − P(G / e, k). Colorings of G − e either give the endpoints of e different colors (colorings of G) or the same color (colorings of G / e, where the two endpoints are merged).

from itertools import product

def colorable(adj, k):
    """Backtracking: try to color the vertices in order with k colors."""
    order, color = list(adj), {}
    def place(i):
        if i == len(order):
            return True
        v = order[i]
        for c in range(k):
            if all(color.get(w) != c for w in adj[v]):
                color[v] = c
                if place(i + 1):
                    return True
                del color[v]                               # backtrack
        return False
    return place(0)

def chromatic_number(adj):
    return next(k for k in range(1, len(adj) + 1) if colorable(adj, k))

def build(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

wheel = lambda n: build([(i, (i + 1) % n) for i in range(n)] + [(i, "hub") for i in range(n)])
petersen = build([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
                 + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])
print(chromatic_number(wheel(6)), chromatic_number(wheel(5)), chromatic_number(petersen))   # 3 4 3

# Count proper 3-colorings of C5 by brute force and compare with (k-1)^n + (-1)^n (k-1)
C5 = [(i, (i + 1) % 5) for i in range(5)]
count = sum(all(c[u] != c[v] for u, v in C5) for c in product(range(3), repeat=5))
print(count, (3 - 1) ** 5 + (-1) ** 5 * (3 - 1))           # 30 30

Key takeaways

χ(G) is the fewest colors in a proper coloring.
ω(G) ≤ χ(G) ≤ Δ(G) + 1, and Brooks improves the upper bound to Δ except for complete graphs and odd cycles.
χ ≤ 2 exactly for bipartite graphs, and deciding χ ≤ 3 is NP-complete.
The chromatic polynomial counts colorings, and deletion–contraction computes it.

Practice

(Beginner) Find χ for K_{3,4}, C₉, W₈, W₉, and the graph formed by two triangles sharing an edge.

(Intermediate) Prove that χ(G) · α(G) ≥ n, and use it to show that χ(C₇ complement) ≥ 4. Then verify P(C₄, k) = (k − 1)⁴ + (k − 1) using deletion–contraction on one edge.

(Interview) Model a Sudoku puzzle as a graph coloring problem. How many vertices and edges does the graph have, what is its chromatic number, and how does a solver use the given digits? Hint: 81 cells, each adjacent to the other cells in its row, column and box (20 neighbors each, so 81 · 20 / 2 = 810 edges). The given digits are a precoloring, and the solver extends it by backtracking with constraint propagation.

Four Color Theorem

Why. In 1852, Francis Guthrie noticed that four colors were enough to color the counties of England so that neighboring counties differ. He asked whether four colors suffice for every map. The question took 124 years to answer. Its proof was the first major theorem proved with essential computer help, which started a debate about what counts as a proof. The ideas developed along the way (Kempe chains, discharging, reducible configurations) shaped much of graph theory.

What. Turn a map into a graph: one vertex per region, and an edge between two regions that share a border segment (meeting at a single point does not count). This graph is planar. It is the dual of the map.

Four Color Theorem (Appel and Haken, 1976). Every planar graph is 4-colorable. Equivalently, every map can be colored with 4 colors so that neighboring regions get different colors.

Four colors are sometimes necessary. K₄ is planar, and the map below has four regions that all touch each other:

   ┌─────────────────────────┐
   │            A            │       A borders B, C and D
   │    ┌───────────────┐    │       B borders C and D
   │    │       B       │    │       C borders D
   │    ├───────┬───────┤    │
   │    │   C   │   D   │    │       dual graph = K₄, so 4 colors are needed
   └────┴───────┴───────┴────┘

History.

Year	Event
1852	Guthrie poses the problem
1879	Kempe publishes a "proof"
1890	Heawood finds the error in Kempe's argument and uses Kempe's ideas to prove that five colors always suffice
1976	Appel and Haken prove four colors suffice, checking 1,936 configurations by computer
1997	Robertson, Sanders, Seymour and Thomas give a simpler proof with 633 configurations, still computer-assisted
2005	Gonthier verifies the proof completely in the Coq proof assistant

The six color theorem (easy). Every planar graph is 6-colorable. Proof by induction on n. By Euler's formula, a planar graph has a vertex v of degree at most 5. Remove v, 6-color the rest by the induction hypothesis (it is still planar), and put v back: its at most 5 neighbors leave one of the 6 colors free.

The five color theorem (idea). Again remove a vertex v of degree at most 5 and color the rest. If its neighbors use only 4 colors, you are done. Otherwise its five neighbors v₁, …, v₅ (in clockwise order) use all five colors. Consider the Kempe chain of v₁: the vertices reachable from v₁ using only the colors of v₁ and v₃. If it does not contain v₃, swap the two colors on the chain, which frees v₁'s color for v. If it does contain v₃, the chain together with v forms a closed curve that separates v₂ from v₄. So the chain of v₂ and v₄ cannot reach v₄, and swapping that chain frees v₂'s color. Kempe's attempt to push this argument to four colors had a subtle gap.

How. The six-color proof is an algorithm. Repeatedly remove a vertex of minimum degree (smallest-last order), then color the vertices greedily in the reverse order. Each vertex has at most 5 neighbors colored before it, so this uses at most 6 colors on any planar graph, in linear time. Efficient algorithms also exist for 5 colors, and a quadratic-time 4-coloring algorithm follows from the 1997 proof.

def smallest_last_coloring(adj):
    """Greedy coloring in reverse smallest-last order. At most 6 colors on any planar graph."""
    remaining = {v: set(ns) for v, ns in adj.items()}
    removal = []
    while remaining:
        v = min(remaining, key=lambda x: len(remaining[x]))   # degree <= 5 in any planar graph
        removal.append(v)
        for w in remaining.pop(v):
            remaining[w].discard(v)
    color = {}
    for v in reversed(removal):                                # each v sees <= 5 colored neighbors
        used = {color[w] for w in adj[v] if w in color}
        color[v] = next(c for c in range(len(adj)) if c not in used)
    return color

# Icosahedron: top 0, upper ring 1..5, lower ring 6..10, bottom 11. 5-regular and planar.
ico = {v: set() for v in range(12)}
def link(u, v):
    ico[u].add(v); ico[v].add(u)
for i in range(5):
    link(0, 1 + i); link(11, 6 + i)
    link(1 + i, 1 + (i + 1) % 5); link(6 + i, 6 + (i + 1) % 5)              # the two rings
    link(1 + i, 6 + i); link(1 + i, 6 + (i + 1) % 5)                       # zigzag between the rings
print(sum(map(len, ico.values())) // 2, 3 * 12 - 6)                       # 30 30   a maximal planar graph
coloring = smallest_last_coloring(ico)
print(len(set(coloring.values())))                                         # 4
print(all(coloring[u] != coloring[v] for u in ico for v in ico[u]))        # True

Key takeaways

Every planar graph, and so every map, can be colored with 4 colors. Four is sometimes needed (K₄).
Six colors are easy (a vertex of degree at most 5 always exists), and five colors follow from Kempe chains.
The four-color proof checks hundreds of configurations by computer, and has been formally verified.
The theorem applies only to planar graphs. Conflict graphs in practice are usually not planar.

Practice

(Beginner) Draw the dual graph of a map of your choice with at least six regions (for example, a few neighboring countries), and 4-color it.

(Intermediate) Write out the six color theorem proof in full, using strong induction (3.2) and the corollary of Euler's formula. Where exactly is planarity used, and why does removing a vertex keep the graph planar?

(Interview) A colleague says, "Our exam-conflict graph only needs 4 time slots, by the Four Color Theorem." What is wrong with this argument, and what would you check? Hint: the theorem needs a planar graph, and a conflict graph containing K₅ (five courses taken together by one student) needs 5 slots. Check for large cliques, or test planarity.

Edge Coloring

Why. In a round-robin tournament, every team plays every other team once, and a team cannot play two matches in the same round. How many rounds are needed? Similar problems arise when scheduling one-on-one meetings, assigning time slots to links in a network where each node can use one link at a time, and routing data through switches. In each case, the edges (matches, meetings, transmissions) get the colors, and edges that share a vertex must differ.

What. A proper edge coloring gives every edge a color so that edges sharing an endpoint get different colors. Each color class is a matching (8.6). The chromatic index χ'(G) is the fewest colors needed.

Edge coloring is vertex coloring of the line graph L(G), whose vertices are the edges of G and whose edges join edges of G that share an endpoint.

Bounds. The edges at a vertex of maximum degree need Δ different colors, so χ'(G) ≥ Δ. For edges, the upper bound is surprisingly tight:

Vizing's theorem (1964): every simple graph has Δ ≤ χ'(G) ≤ Δ + 1. Graphs with χ' = Δ are class 1, and graphs with χ' = Δ + 1 are class 2. Deciding which class a graph belongs to is NP-complete.
König's theorem (1916): every bipartite graph has χ'(G) = Δ.

Graph	`Δ`	`χ'`
`Cₙ`, `n` even	2	2
`Cₙ`, `n` odd	2	3
`Kₙ`, `n` even	`n − 1`	`n − 1`
`Kₙ`, `n` odd	`n − 1`	`n`
`K_{m,n}`	`max(m, n)`	`max(m, n)` (König)
Petersen graph	3	4

Round-robin tournaments. With n teams (n even), the matches are the edges of Kₙ, and the rounds are the colors, so n − 1 rounds suffice. In each round, every team plays exactly once (each color class is a perfect matching). The circle method constructs the schedule. Fix team n − 1 in the center and place the others on a circle. In round r, the center plays team r, and the remaining teams pair up symmetrically across the circle. Then rotate. For odd n, add a dummy team: whoever "plays" it has a bye, so n rounds are needed, matching χ'(Kₙ) = n.

def round_robin(n):
    """Circle method for an even number n of teams: a proper (n-1)-edge-coloring of K_n."""
    rounds = []
    for r in range(n - 1):
        matches = [(r, n - 1)]                                   # the fixed team plays team r
        for i in range(1, n // 2):
            matches.append(((r + i) % (n - 1), (r - i) % (n - 1)))   # pairs symmetric around r
        rounds.append(matches)
    return rounds

schedule = round_robin(6)
for r, matches in enumerate(schedule, 1):
    print(r, matches)
# 1 [(0, 5), (1, 4), (2, 3)]
# 2 [(1, 5), (2, 0), (3, 4)]
# 3 [(2, 5), (3, 1), (4, 0)]
# 4 [(3, 5), (4, 2), (0, 1)]
# 5 [(4, 5), (0, 3), (1, 2)]

all_matches = [frozenset(m) for rnd in schedule for m in rnd]
print(len(all_matches), len(set(all_matches)))                   # 15 15   every pair exactly once
print(all(len({t for m in rnd for t in m}) == 6 for rnd in schedule))   # True   each team once per round

Key takeaways

Edge coloring gives edges at a common vertex different colors, and each color class is a matching.
Vizing: χ'(G) is Δ or Δ + 1. König: bipartite graphs always need exactly Δ.
χ'(Kₙ) = n − 1 for even n and n for odd n, which is the number of rounds in a round-robin tournament.
Edge coloring of G is vertex coloring of the line graph L(G).

Practice

(Beginner) Find χ' for K₄, C₅, K_{2,3} and W₄, and give an optimal edge coloring for each.

(Intermediate) Prove that χ'(Kₙ) ≥ n when n is odd. Hint: a matching in Kₙ has at most (n − 1)/2 edges, and Kₙ has n(n − 1)/2 edges.

(Interview) Each of 10 engineers must have a one-on-one meeting with each of 4 managers, every meeting takes one hour, and a person can attend only one meeting per hour. What is the minimum number of hours, and how would you build the schedule? Hint: the meetings form the bipartite graph K_{4,10} with Δ = 10. König's theorem says 10 hours suffice. Build it by repeatedly removing a matching that covers every vertex of maximum degree, or by a direct rotation.

8.6 Matchings and Flows

The last subchapter is about pairing things up and moving things through networks. Matchings model assignments, and Hall's theorem says exactly when a complete assignment exists. Network flows model throughput, and the max-flow min-cut theorem connects the most you can push through a network with its narrowest bottleneck. Both are special cases of one idea: a maximum is certified by a matching minimum.

Matchings

Why. Assigning workers to tasks, students to project slots, drivers to riders, donors to patients: each is a set of possible pairs, and each person can be in at most one chosen pair. The goal is to make as many pairs as possible. Greedy choices can paint you into a corner, and the theory of matchings explains how to get out of it.

What. A matching M in a graph is a set of edges no two of which share an endpoint. A vertex touched by an edge of M is matched (saturated), and the others are free.

Term	Meaning
Maximal matching	No edge can be added to it
Maximum matching	Has the largest possible number of edges, `ν(G)`
Perfect matching	Every vertex is matched, so `

Every maximum matching is maximal, but not conversely. In the path a, b, c, d, the matching {{b, c}} is maximal (both other edges touch it) but not maximum: {{a, b}, {c, d}} is larger, and it is perfect.

Augmenting paths. An alternating path uses edges that are alternately outside and inside M. An augmenting path is an alternating path that starts and ends at free vertices. Flipping it, that is, swapping its matched and unmatched edges, gives a matching with one more edge:

   matching M (═) and an augmenting path from x to y

   x ─── a ═══ b ─── c ═══ d ─── y          |M ∩ path| = 2
   free                          free

   after flipping the path (M Δ path)

   x ═══ a ─── b ═══ c ─── d ═══ y          |M ∩ path| = 3

Berge's theorem (1957). A matching is maximum if and only if there is no augmenting path for it.

Proof sketch. If an augmenting path exists, flipping it gives a larger matching. Conversely, suppose M' is larger than M. In the symmetric difference M Δ M', every vertex has degree at most 2, so it splits into alternating paths and even cycles. Cycles contain equally many edges of M and M', so some path contains more edges of M' than of M. That path starts and ends with M' edges at vertices that are free in M: it is augmenting.

How. Berge's theorem gives an algorithm: start with any matching and repeatedly find and flip an augmenting path.

Bipartite graphs, Kuhn's algorithm: for each vertex on the left, search for an augmenting path with DFS. O(nm).
Bipartite graphs, Hopcroft–Karp: find many shortest augmenting paths per phase. O(m √n).
General graphs, Edmonds' blossom algorithm (1965): odd cycles ("blossoms") complicate the search, and Edmonds handles them by shrinking them. Polynomial time.
Weighted bipartite matching (the assignment problem): the Hungarian algorithm, O(n³).

König's theorem. In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover (a set of vertices touching every edge). In general graphs, only ν(G) ≤ minimum vertex cover holds: K₃ has ν = 1 but needs 2 vertices to cover its edges.

def max_bipartite_matching(adj):
    """Kuhn's algorithm. adj: left vertex -> list of right vertices. Returns (size, right -> left)."""
    match = {}

    def try_assign(u, seen):                     # DFS for an augmenting path starting at u
        for v in adj[u]:
            if v in seen:
                continue
            seen.add(v)
            if v not in match or try_assign(match[v], seen):   # v is free, or its partner can move
                match[v] = u                     # flip the path: u takes v
                return True
        return False

    size = sum(try_assign(u, set()) for u in adj)
    return size, match

skills = {"Ana": ["Backend", "Data"], "Ben": ["Backend"],
          "Cleo": ["Data", "Ops"], "Dev": ["Ops", "Frontend"]}
size, match = max_bipartite_matching(skills)
print(size, {worker: job for job, worker in sorted(match.items(), key=lambda p: p[1])})
# 4 {'Ana': 'Data', 'Ben': 'Backend', 'Cleo': 'Ops', 'Dev': 'Frontend'}

When Ben arrives, his only job, Backend, is already taken by Ana. The augmenting path Ben – Backend ═ Ana – Data moves Ana to Data and frees Backend for Ben.

Key takeaways

A matching is a set of disjoint edges. Maximal means nothing can be added. Maximum means the largest size. Perfect means every vertex is matched.
Berge: a matching is maximum exactly when no augmenting path exists. Flipping an augmenting path adds one edge.
Bipartite matching takes O(nm) with Kuhn's algorithm and O(m √n) with Hopcroft–Karp. General graphs need Edmonds' blossom algorithm.
König: in bipartite graphs, maximum matching size equals minimum vertex cover size.

Practice

(Beginner) Find a maximal matching that is not maximum in P₆ and in C₆. What is ν for Kₙ, Cₙ, K_{m,n} and the Petersen graph?

(Intermediate) Prove that every maximal matching has at least half as many edges as a maximum matching. Hint: every edge of a maximum matching shares an endpoint with some edge of the maximal matching, and each maximal-matching edge has only two endpoints.

(Interview) A ride-hailing service must pair waiting riders with nearby drivers every few seconds, where each driver can take one rider. How would you maximize the number of pairs, and what changes if you also want to minimize the total pickup distance? Hint: the first is maximum bipartite matching (Hopcroft–Karp). The second is the assignment problem (Hungarian algorithm or min-cost flow). In practice, batching windows trade waiting time for better matches.

Hall's Marriage Theorem

Why. Before searching for a complete assignment, it helps to know whether one can exist. If it cannot, a manager wants a reason, not just "the algorithm failed". Hall's theorem gives a condition that is necessary and sufficient, and whenever a complete assignment is impossible, it points to a small group of people who are competing for too few positions.

What. Let G be a bipartite graph with parts X and Y. For S ⊆ X, let N(S) be the set of vertices in Y adjacent to at least one vertex of S. A matching saturates X if it matches every vertex of X.

Hall's theorem (1935). G has a matching that saturates X if and only if

  |N(S)| ≥ |S|        for every subset S ⊆ X        (Hall's condition)

Necessity is obvious: the vertices of S must be matched to |S| different vertices, all in N(S).

Sufficiency (proof sketch by strong induction on |X|). Two cases.

If every non-empty proper subset S has |N(S)| ≥ |S| + 1 (some slack), match any vertex x ∈ X to any neighbor y. Removing x and y costs every remaining set at most one neighbor, so Hall's condition still holds, and the induction hypothesis matches the rest.
If some non-empty proper subset S is tight, |N(S)| = |S|, then match S into N(S) by induction. In the rest of the graph (X − S and Y − N(S)), Hall's condition still holds: if a set T ⊆ X − S had fewer than |T| new neighbors, S ∪ T would violate the condition in G. Match the rest by induction too.

Hall's theorem also follows from König's theorem or from max-flow min-cut (next topics).

Example.

   applicant   acceptable positions
       A       1, 2                     N({A, B, C}) = {1, 2}
       B       1                        three applicants compete for two positions,
       C       1, 2                     so Hall's condition fails for S = {A, B, C}
       D       2, 3, 4

Whatever happens, one of A, B, C is left without a position. The deficiency version of Hall's theorem says that the maximum matching has size |X| − max_S (|S| − |N(S)|) = 4 − 1 = 3.

Corollaries.

Every k-regular bipartite graph with k ≥ 1 has a perfect matching. For any S ⊆ X, the k|S| edges leaving S all land in N(S), which receives at most k|N(S)| edges, so |N(S)| ≥ |S|. Removing a perfect matching leaves a (k − 1)-regular bipartite graph, so repeating this gives König's edge coloring theorem (8.5) for regular bipartite graphs.
Systems of distinct representatives: sets A₁, …, Aₙ have distinct representatives aᵢ ∈ Aᵢ exactly when every union of k of them has at least k elements.

from itertools import combinations

def hall_violation(adj):
    """Return a subset S of the left side with the largest deficiency |S| - |N(S)|, or None."""
    worst, worst_def = None, 0
    left = sorted(adj)
    for k in range(1, len(left) + 1):
        for S in combinations(left, k):                  # 2^|X| subsets: fine for small X
            N = set().union(*(adj[x] for x in S))
            if len(S) - len(N) > worst_def:
                worst, worst_def = (S, sorted(N)), len(S) - len(N)
    return worst, worst_def

accepts = {"A": {1, 2}, "B": {1}, "C": {1, 2}, "D": {2, 3, 4}}
print(hall_violation(accepts))                           # ((('A', 'B', 'C'), [1, 2]), 1)
print(len(accepts) - hall_violation(accepts)[1])         # 3   = size of a maximum matching

accepts["C"].add(3)                                      # C now also accepts position 3
print(hall_violation(accepts))                           # (None, 0)   Hall's condition holds

Key takeaways

A matching saturating X exists exactly when every S ⊆ X has at least |S| neighbors.
A violating set S is a short certificate that no complete assignment exists.
The maximum matching size is |X| minus the largest deficiency |S| − |N(S)|.
Every k-regular bipartite graph has a perfect matching.

Practice

(Beginner) Check Hall's condition for X = {a, b, c} with N(a) = {1, 2}, N(b) = {2, 3}, N(c) = {1, 3}, and find a matching saturating X. Then change N(c) to {2} and find a violating set.

(Intermediate) Prove that every k-regular bipartite graph (k ≥ 1) has a perfect matching, and conclude that its edges can be colored with k colors.

(Interview) Remove two diagonally opposite corner squares from an 8 × 8 chessboard. Can the remaining 62 squares be covered by 31 dominoes? Explain the answer in the language of Hall's theorem. Hint: squares are vertices and dominoes are edges of a bipartite graph between black and white squares. Count the squares of each color: the larger color class cannot be matched into the smaller.

Network Flows

Why. Oil through pipelines, packets through a network, cars through a city, goods through a supply chain: each link carries at most a certain amount per unit time, and the question is how much can get from a source to a destination. Network flow answers it efficiently. It is also a modeling tool: bipartite matching, edge-disjoint paths, scheduling with capacities, and image segmentation can all be reduced to a maximum flow problem.

What. A flow network is a directed graph with a source s, a sink t, and a capacity c(u, v) ≥ 0 on each arc. A flow assigns a number f(u, v) to each arc so that

Capacity constraint: 0 ≤ f(u, v) ≤ c(u, v).
Conservation: at every vertex other than s and t, the flow in equals the flow out.

The value |f| of a flow is the net flow out of s, which by conservation equals the net flow into t. The maximum flow problem asks for a flow of largest value.

Analogy. Water pipes of different widths. Water enters at the source and leaves at the sink, no junction leaks or stores water, and no pipe carries more than its width allows.

Residual graph. Given a flow f, the residual graph describes how the flow can still change:

a forward residual arc u → v with capacity c(u, v) − f(u, v) (room to push more), and
a backward residual arc v → u with capacity f(u, v) (flow that can be cancelled, which redirects it).

An augmenting path is an s–t path in the residual graph. Pushing its smallest residual capacity (the bottleneck) along it increases |f|. The backward arcs matter: without them, a bad first choice could never be undone.

How.

Ford–Fulkerson method (1956): start with the zero flow and repeatedly augment along any augmenting path until none exists. With integer capacities, each augmentation adds at least 1, so it terminates.
Edmonds–Karp algorithm: always choose a shortest augmenting path (BFS, 8.4). This guarantees O(nm²) time for any capacities.
Faster algorithms exist: Dinic's algorithm, O(n²m), push–relabel, and recent almost-linear-time algorithms (2022).

Integrality theorem. If all capacities are integers, there is a maximum flow in which every f(u, v) is an integer, and Ford–Fulkerson finds one. This is what makes reductions to flow work for discrete problems.

Reductions.

Problem	Flow model
Bipartite matching	`s → x` for each `x ∈ X`, `x → y` for each edge, `y → t` for each `y ∈ Y`, all capacity 1. Max flow = maximum matching
Several sources or sinks	Add a super-source joined to every source, and a super-sink, with infinite capacities
Vertex capacities	Split `v` into `v_in → v_out` with the vertex's capacity on that arc
Edge-disjoint `s`–`t` paths	Capacity 1 on every arc. Max flow = number of disjoint paths (Menger, 8.3)

Example.

                10              4               10
          s ──────────► a ──────────► b ──────────► t
           ╲            │ ╲           ▲             ▲
            ╲ 10      2 │  ╲ 8        │ 6           │
             ╲          ▼   ╲         │             │ 10
              ╰───────► c    ╰──────► d ────────────╯
                        │             ▲
                        ╰───── 9 ─────╯

The arcs are s→a (10), s→c (10), a→b (4), a→c (2), a→d (8), c→d (9), d→b (6), b→t (10) and d→t (10).

from collections import deque, defaultdict

def max_flow(arcs, s, t):
    """Edmonds–Karp. arcs: list of (u, v, capacity). Returns (value, residual capacities, reachable set)."""
    res = defaultdict(lambda: defaultdict(int))
    for u, v, c in arcs:
        res[u][v] += c                           # forward residual capacity
        res[v][u] += 0                           # create the backward residual arc
    value = 0
    while True:
        parent = {s: None}
        queue = deque([s])
        while queue and t not in parent:         # BFS: shortest augmenting path
            u = queue.popleft()
            for v, r in res[u].items():
                if r > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)
        if t not in parent:
            return value, res, set(parent)       # no augmenting path: the flow is maximum
        bottleneck, v = float("inf"), t
        while parent[v] is not None:
            bottleneck = min(bottleneck, res[parent[v]][v])
            v = parent[v]
        v = t
        while parent[v] is not None:             # push the bottleneck along the path
            u = parent[v]
            res[u][v] -= bottleneck
            res[v][u] += bottleneck              # allow it to be cancelled later
            v = u
        value += bottleneck

arcs = [("s", "a", 10), ("s", "c", 10), ("a", "b", 4), ("a", "c", 2), ("a", "d", 8),
        ("c", "d", 9), ("d", "b", 6), ("b", "t", 10), ("d", "t", 10)]
value, res, reachable = max_flow(arcs, "s", "t")
print(value)                                                     # 19
print({f"{u}{v}": c - res[u][v] for u, v, c in arcs})            # flow on each arc
# {'sa': 10, 'sc': 9, 'ab': 4, 'ac': 0, 'ad': 6, 'cd': 9, 'db': 5, 'bt': 9, 'dt': 10}
print(sorted(reachable))                                         # ['c', 's']   source side of a minimum cut

Check conservation at d: in 6 + 9 = 15, out 5 + 10 = 15. The vertex c can forward at most 9 units, through c → d, so s → c can never be used to its full capacity of 10.

Key takeaways

A flow respects arc capacities and is conserved at every vertex except s and t.
The residual graph has forward arcs (spare capacity) and backward arcs (flow that can be cancelled).
Ford–Fulkerson augments along residual paths until none remain. Edmonds–Karp uses BFS and runs in O(nm²).
With integer capacities, some maximum flow is integral, so matchings and disjoint paths reduce to flows.

Practice

(Beginner) In the example network, check that the flow printed above satisfies the capacity constraints and conservation at a, b, c and d.

(Intermediate) Show how to reduce maximum bipartite matching to maximum flow, and prove that an integral maximum flow gives a maximum matching. Then show how to handle a vertex that can carry at most k units of flow.

(Interview) A company must decide which of several projects to run. Each project has a profit, each requires some pieces of equipment, and each piece of equipment has a cost (paid once, shared by all projects that use it). How can this be solved with a minimum cut? Hint: this is the project selection problem. Join s to each project with its profit, each piece of equipment to t with its cost, and each project to its equipment with infinite capacity. The best net profit is the total profit minus the minimum cut.

Max-Flow Min-Cut Theorem

Why. The Edmonds–Karp run above stopped at 19 units. How do we know that 19 is the best possible, and not just the best this algorithm found? The max-flow min-cut theorem gives a certificate: a set of arcs whose total capacity is 19 and that every unit of flow must cross. It is one of the central theorems of combinatorial optimization, an instance of linear programming duality, and it implies Menger's, König's and Hall's theorems.

What. An s–t cut is a partition of the vertices into S and T = V − S with s ∈ S and t ∈ T. Its capacity is the total capacity of the arcs going from S to T:

  c(S, T) = Σ_{u ∈ S, v ∈ T} c(u, v)

Arcs from T back to S do not count.

Weak duality. For every flow f and every cut (S, T), |f| ≤ c(S, T).

Proof. Summing conservation over the vertices of S shows that |f| equals the flow from S to T minus the flow from T to S. The first term is at most c(S, T) and the second is at least 0.

So every cut capacity is an upper bound on every flow value. The theorem says the best of these bounds is exact.

Max-flow min-cut theorem (Ford and Fulkerson, 1956). The maximum value of an s–t flow equals the minimum capacity of an s–t cut. More precisely, the following are equivalent for a flow f:

f is a maximum flow.
The residual graph has no augmenting path.
|f| = c(S, T) for some cut (S, T).

Proof. (1 ⇒ 2) An augmenting path would increase the flow. (3 ⇒ 1) No flow can exceed c(S, T), by weak duality. (2 ⇒ 3) Let S be the set of vertices reachable from s in the residual graph, and T the rest. Then t ∈ T, because no augmenting path exists. Every arc from S to T must be saturated (f = c), since otherwise its head would be reachable. Every arc from T to S must carry zero flow, since otherwise its backward residual arc would make its tail reachable. So the net flow across the cut is exactly c(S, T).

The proof gives an algorithm: after Ford–Fulkerson stops, one last search from s in the residual graph finds a minimum cut, in O(m) time.

Example. In the network of the previous topic, the residual search reaches only s and c, so the minimum cut is S = {s, c}. Its arcs are s → a (10) and c → d (9), with capacity 19, equal to the flow value. Other cuts are larger:

`S`	Arcs from `S` to `T`	Capacity
`{s}`	`s→a`, `s→c`	20
`{s, c}`	`s→a`, `c→d`	19
`{s, a}`	`s→c`, `a→b`, `a→c`, `a→d`	24
`{s, a, c}`	`a→b`, `a→d`, `c→d`	21
`{s, a, c, d}`	`a→b`, `d→b`, `d→t`	20
`{s, a, b, c, d}`	`b→t`, `d→t`	20

from itertools import combinations

arcs = [("s", "a", 10), ("s", "c", 10), ("a", "b", 4), ("a", "c", 2), ("a", "d", 8),
        ("c", "d", 9), ("d", "b", 6), ("b", "t", 10), ("d", "t", 10)]
inner = ["a", "b", "c", "d"]

def cut_capacity(S):
    return sum(c for u, v, c in arcs if u in S and v not in S)    # only arcs from S to T count

cuts = [{"s", *extra} for k in range(len(inner) + 1) for extra in combinations(inner, k)]
best = min(cuts, key=cut_capacity)
print(len(cuts), sorted(best), cut_capacity(best))                # 16 ['c', 's'] 19
print(sorted(cut_capacity(S) for S in cuts))
# [19, 20, 20, 20, 21, 24, 26, 27, 29, 30, 30, 30, 32, 32, 36, 40]

Consequences.

Menger's theorem (8.3): with capacity 1 on every edge, a maximum flow is a set of edge-disjoint paths and a minimum cut is a smallest separating edge set.
König's and Hall's theorems: in the matching network, a minimum cut corresponds to a minimum vertex cover, and a cut smaller than |X| exhibits a set violating Hall's condition.
Applications: network reliability (minimum number of links whose failure separates two sites), image segmentation (separating foreground from background pixels with a minimum cut), baseball elimination, and airline scheduling.

Key takeaways

A cut separates s from t, and its capacity counts only arcs from the s side to the t side.
Every flow is at most every cut (weak duality), and the maximum flow equals the minimum cut.
When no augmenting path remains, the vertices reachable from s in the residual graph form a minimum cut.
The theorem certifies optimality, and it implies Menger's, König's and Hall's theorems.

Practice

(Beginner) Compute the capacity of the cuts S = {s, a, b} and S = {s, c, d} in the example network, and check that both are at least 19.

(Intermediate) Prove weak duality carefully: show that for every cut (S, T), the value |f| equals the flow from S to T minus the flow from T to S. Hint: add up the conservation equations of all vertices in S. Arcs with both ends in S cancel.

(Interview) Two data centers are connected through a mesh of routers and links. Management asks for the smallest number of links whose simultaneous failure would cut them off from each other, and for the actual list of links. How do you compute both? Hint: give every link capacity 1 (an undirected link becomes two opposite arcs) and run max flow between the two data centers. The flow value is the number, and the arcs leaving the residual-reachable set are the list.

← Discrete Mathematics

8. Graph Theory

8.1 Graph Fundamentals

Graph Terminology

What. A graph G = (V, E) consists of

a non-empty set V of vertices (also called nodes), and
a set E of edges, where each edge e = {u, v} connects two vertices.

In this chapter, V is finite, n = |V| is the order of the graph, and m = |E| is its size.

Term	Meaning
Endpoints	`u` and `v` are the endpoints of the edge `{u, v}`
Adjacent (neighbors)	`u` and `v` are adjacent if `{u, v} ∈ E`
Incident	An edge is incident to each of its endpoints
Neighborhood `N(v)`	The set of all neighbors of `v`
Loop	An edge from a vertex to itself
Multiple (parallel) edges	Two or more edges with the same endpoints
Isolated vertex	A vertex with no neighbors
Weighted graph	A graph with a number `w(e)` (cost, length, capacity) on each edge

Graphs come in several flavors, depending on which of these features are allowed:

Type	Edges	Multiple edges?	Loops?
Simple graph	Undirected	No	No
Multigraph	Undirected	Yes	No
Pseudograph	Undirected	Yes	Yes
Simple directed graph	Directed	No	Yes
Directed multigraph	Directed	Yes	Yes

Unless stated otherwise, "graph" means a simple graph. A simple graph has at most one edge per pair of distinct vertices, so

  0 ≤ m ≤ C(n, 2) = n(n − 1)/2

Example.

     a ─────── b
     │       ╱
     │     ╱           e        V = {a, b, c, d, e}
     │   ╱                      E = {{a, b}, {a, c}, {b, c}, {c, d}}
     c ─────── d                n = 5, m = 4

Here a and b are adjacent, the edge {c, d} is incident to c and to d, N(c) = {a, b, d}, and e is isolated.

V = {"a", "b", "c", "d", "e"}
E = {frozenset(p) for p in [("a", "b"), ("a", "c"), ("b", "c"), ("c", "d")]}   # unordered pairs

def neighbors(v):
    return {w for e in E if v in e for w in e if w != v}

print(sorted(neighbors("c")))                       # ['a', 'b', 'd']
print(frozenset({"b", "a"}) in E)                   # True: {a, b} and {b, a} are the same edge
print([v for v in sorted(V) if not neighbors(v)])   # ['e']   isolated vertices
print(len(E), len(V) * (len(V) - 1) // 2)           # 4 10    m versus the maximum C(n, 2)

Key takeaways

A graph is a pair (V, E): vertices and the edges between them. Only the connections matter, not the drawing.
A simple graph has no loops and no multiple edges, so it has at most C(n, 2) edges.
Adjacent vertices share an edge. An edge is incident to its endpoints. N(v) is the set of neighbors of v.
Real-world graphs are usually sparse, and this drives the choice of data structures (8.2).

Practice

(Beginner) Draw the graph with V = {1, 2, 3, 4, 5, 6} where {i, j} is an edge whenever i ≠ j and i divides j. List N(1), N(6), and any isolated vertices.

(Intermediate) How many different simple graphs can be built on the labeled vertex set {1, …, n}? How many of them have exactly k edges? Hint: each of the C(n, 2) possible edges is either present or absent (5.1).

(Interview) You are modeling a city's bike-sharing system to answer "which stations are reachable from here within 10 minutes". What are the vertices and edges, are the edges weighted, and is the graph simple? Hint: think about what a trip looks like, whether two different routes can join the same pair of stations, and whether a trip from a station back to itself matters.

Directed and Undirected Graphs

	Undirected graph	Directed graph
Edge	Unordered pair `{u, v}`	Ordered pair `(u, v)`
Picture	`u ──── v`	`u ───► v`
Neighbors	`N(v)`	Out-neighbors `N⁺(v)` and in-neighbors `N⁻(v)`
Degree	`deg(v)`	Out-degree `deg⁺(v)` and in-degree `deg⁻(v)`
As a relation	Symmetric and irreflexive	Any relation
Typical examples	Friendship, road with two-way traffic, chemical bond	Follows, hyperlinks, dependencies, one-way streets
Maximum edges (simple, no loops)	`n(n − 1)/2`	`n(n − 1)`

Example: a follow graph.

     ana ─────► ben
      ▲  ◄───── │
      │         │         ana → ben, ben → ana   (mutual)
      │         ▼         ben → dev, dev → cleo, cleo → ana
     cleo ◄──── dev

follows = {                       # out-neighbors: who each user follows
    "ana": {"ben"},
    "ben": {"ana", "dev"},
    "cleo": {"ana"},
    "dev": {"cleo"},
}

def followers(user):              # in-neighbors: scan every out-list
    return {u for u, outs in follows.items() if user in outs}

mutual = {frozenset((u, v)) for u, outs in follows.items() for v in outs if u in follows[v]}
underlying = {frozenset((u, v)) for u, outs in follows.items() for v in outs}

print(sorted(followers("ana")))   # ['ben', 'cleo']
print([sorted(e) for e in mutual])            # [['ana', 'ben']]
print(sum(map(len, follows.values())), len(underlying))   # 5 4   two opposite arcs merge into one edge

Key takeaways

Directed edges are ordered pairs u → v. Undirected edges are unordered pairs {u, v}.
A directed graph is a relation on V. An undirected simple graph is a symmetric, irreflexive relation.
Every directed concept splits in two: in- and out-neighbors, in- and out-degree.
Forgetting directions gives the underlying undirected graph, and opposite arcs merge into one edge.

Practice

(Beginner) For the follow graph above, list N⁺(v) and N⁻(v) for every vertex. Which user follows the most people, and which has the most followers?

(Intermediate) How many directed graphs without loops are there on n labeled vertices? How many with loops allowed? How many of the loop-free ones are symmetric? Hint: count the possible arcs, then apply the product rule (5.1).

(Interview) A social network stores only out-lists (who I follow). The product team wants a "followers" page and a "mutual friends" badge. What would you precompute, and how much extra storage does it cost? Hint: the reverse graph has the same number of arcs. A mutual pair is an arc whose reverse is also present.

Degree and Handshaking Lemma

Handshaking lemma. In every undirected graph,

  Σ_{v ∈ V} deg(v) = 2m

Directed version. Each arc contributes 1 to the out-degree of its tail and 1 to the in-degree of its head, so

  Σ_{v ∈ V} deg⁺(v) = Σ_{v ∈ V} deg⁻(v) = m

Example. Can 7 people each shake hands with exactly 3 others? The degree sum would be 7 · 3 = 21, which is odd. So it is impossible, however the handshakes are arranged.

def degrees(n, edges):
    deg = [0] * n
    for u, v in edges:
        deg[u] += 1
        deg[v] += 1                                # a loop (u == v) correctly adds 2
    return deg

edges = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)]
deg = degrees(5, edges)
print(deg, sum(deg), 2 * len(edges))               # [2, 2, 3, 2, 1] 10 10
print(sum(d % 2 for d in deg))                     # 2   odd-degree vertices: always an even count

def is_graphic(seq):
    """Havel–Hakimi: can a simple graph have exactly these degrees?"""
    seq = sorted(seq, reverse=True)
    while seq and seq[0] > 0:
        d, seq = seq[0], seq[1:]
        if d > len(seq):
            return False                           # not enough other vertices to connect to
        seq = [x - 1 for x in seq[:d]] + seq[d:]   # join the removed vertex to the d largest
        if min(seq) < 0:
            return False
        seq.sort(reverse=True)
    return True

print(is_graphic([3, 3, 2, 2, 2]), is_graphic([3, 3, 3, 1]), is_graphic([3] * 7))   # True False False

Key takeaways

deg(v) counts incident edges, and a loop counts twice.
Handshaking lemma: Σ deg(v) = 2m. In a digraph, the in-degrees and the out-degrees each sum to m.
The number of odd-degree vertices is always even.
An even degree sum is necessary but not sufficient for a sequence to be graphic. Havel–Hakimi decides it.

Practice

(Beginner) A graph has degree sequence (4, 3, 3, 2, 2). How many edges does it have? Is there a graph with degree sequence (5, 3, 3, 2, 2) on 5 vertices?

(Intermediate) Prove that every simple graph with at least 2 vertices has two vertices of the same degree. Hint: the possible degrees are 0, …, n − 1, but 0 and n − 1 cannot both occur. Apply the pigeonhole principle (5.4).

(Interview) The "friendship paradox" says that, on average, your friends have more friends than you do. Make this precise: compare the average degree with the average degree of a randomly chosen endpoint of a random edge. Hint: the second average is Σ deg(v)² / Σ deg(v). Compare it with Σ deg(v) / n, using the fact that a variance is non-negative (7.3).

Special Graphs (Complete, Cycle, Wheel, Hypercube)

What.

The complete graph Kₙ has n vertices and an edge between every pair. It is the densest simple graph.
The cycle Cₙ (n ≥ 3) has vertices v₁, …, vₙ and edges {v₁, v₂}, {v₂, v₃}, …, {vₙ₋₁, vₙ}, {vₙ, v₁}.
The path Pₙ is Cₙ with one edge removed: n vertices in a line.
The wheel Wₙ (n ≥ 3) is Cₙ plus a hub vertex adjacent to all n vertices of the cycle.
The n-cube (hypercube) Qₙ has the 2ⁿ bit strings of length n as vertices. Two strings are adjacent when they differ in exactly one bit.

     K₄                  C₅                  W₅

   a ──── b               1                   1
   │ ╲  ╱ │             ╱   ╲               ╱ │ ╲
   │  ╳   │            5     2             5 ─ h ─ 2
   │ ╱  ╲ │             ╲   ╱              ╲ ╱  ╲ ╱
   c ──── d              4 ─ 3              4 ── 3

     Q₃
          110 ─────────── 111
         ╱ │             ╱ │
      010 ─────────── 011  │
       │   │           │   │
       │  100 ─────────│─ 101
       │ ╱             │ ╱
      000 ─────────── 001

(In W₅, the hub h is joined to all five rim vertices 1, …, 5.)

Graph	Vertices	Edges	Degrees
`Kₙ`	`n`	`n(n − 1)/2`	`n − 1` (regular)
`Cₙ`	`n`	`n`	2 (regular)
`Pₙ`	`n`	`n − 1`	1 at the two ends, 2 elsewhere
`Wₙ`	`n + 1`	`2n`	3 on the rim, `n` at the hub
`Qₙ`	`2ⁿ`	`n · 2ⁿ⁻¹`	`n` (regular)

Each edge count follows from the handshaking lemma. For example, Qₙ has 2ⁿ vertices of degree n, so 2m = n · 2ⁿ.

from itertools import combinations

def complete(n):
    return list(combinations(range(n), 2))

def cycle(n):
    return [(i, (i + 1) % n) for i in range(n)]

def wheel(n):                                       # rim 0 … n−1, hub n
    return cycle(n) + [(i, n) for i in range(n)]

def hypercube(n):
    # u and v differ in exactly one bit  <=>  u XOR v is a power of two
    return [(u, u ^ (1 << b)) for u in range(2 ** n) for b in range(n) if u < u ^ (1 << b)]

for name, edges in [("K6", complete(6)), ("C6", cycle(6)), ("W6", wheel(6)), ("Q4", hypercube(4))]:
    print(name, len(edges))
# K6 15
# C6 6
# W6 12
# Q4 32

print(bin(0b0110 ^ 0b0011).count("1"))             # 2   distance in Q4 between 0110 and 0011

Key takeaways

Kₙ: every pair adjacent, n(n − 1)/2 edges. Cₙ: a ring of n edges. Wₙ: a cycle plus a hub, 2n edges.
Qₙ: bit strings joined when they differ in one bit. It has 2ⁿ vertices, n · 2ⁿ⁻¹ edges, and is n-regular.
Qₙ is built from two copies of Qₙ₋₁, and the distance between two vertices is their Hamming distance.
The handshaking lemma gives every edge count in the table.

Practice

(Beginner) How many vertices and edges do K₁₀, C₁₀, W₁₀ and Q₅ have?

(Intermediate) For which n is Kₙ regular, Wₙ regular, and Cₙ equal to Kₙ? Prove that Qₙ has n · 2ⁿ⁻¹ edges by induction on n (3.2), using the recursive construction.

(Interview) In a hypercube network of 2ⁿ processors, design a routing rule that each processor can apply locally, using only the destination address, to forward a message along a shortest path. How many different shortest paths are there between two processors at distance d? Hint: fix one differing bit per hop. The differing bits can be fixed in any order.

Bipartite Graphs

The complete bipartite graph K_{m,n} has parts of sizes m and n and all mn edges between them.

   K₂,₃                     C₆ (bipartite)              C₅ (not bipartite)

    x₁          x₂             1 ── 2                         1
    ├──── y₁ ───┤            ╱        ╲                    ╱     ╲
    ├──── y₂ ───┤           6          3                  5        2
    └──── y₃ ───┘            ╲        ╱                    ╲      ╱
                               5 ── 4                        4 ── 3

   parts {x₁, x₂}, {y₁, y₂, y₃}   parts {1, 3, 5}, {2, 4, 6}   1, 2, 3, 4, 5 cannot alternate

Theorem. A graph is bipartite if and only if it contains no cycle of odd length.

from collections import deque

def two_color(adj):
    """Return a 2-coloring {v: 0/1}, or None if the graph has an odd cycle."""
    color = {}
    for start in adj:                                # every component needs its own start
        if start in color:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for w in adj[u]:
                if w not in color:
                    color[w] = 1 - color[u]          # opposite side of u
                    queue.append(w)
                elif color[w] == color[u]:
                    return None                      # edge inside one side: odd cycle exists
    return color

def cycle_adj(n):
    return {i: [(i - 1) % n, (i + 1) % n] for i in range(n)}

print(two_color(cycle_adj(6)))                       # {0: 0, 5: 1, 1: 1, 4: 0, 2: 0, 3: 1}
print(two_color(cycle_adj(5)))                       # None

Key takeaways

Bipartite means the vertices split into two parts and every edge crosses between them, which is the same as being 2-colorable.
K_{m,n} has mn edges. Cₙ is bipartite exactly when n is even, and Qₙ is always bipartite (split by the parity of the number of 1s).
A graph is bipartite if and only if it has no odd cycle.
BFS 2-coloring tests bipartiteness in O(n + m).

Practice

(Beginner) Which of these are bipartite: K₃, C₈, W₄, Q₃, K_{1,5}? Give the parts or an odd cycle.

(Intermediate) Prove that a bipartite graph with n vertices has at most ⌊n²/4⌋ edges. When is the bound attained? Hint: with parts of size k and n − k, there are at most k(n − k) edges.

(Interview) You are given n people and a list of pairs who refuse to be on the same team. Decide whether everyone can be split into two teams. What do you report when it is impossible? Hint: this is a bipartiteness test. When it fails, the two BFS paths to the conflicting edge give an odd cycle of mutual dislike, a short certificate.

Subgraphs and Complements

What.

A subgraph of G = (V, E) is a graph H = (W, F) with W ⊆ V and F ⊆ E, where every edge in F has both endpoints in W.
A spanning subgraph keeps all the vertices: W = V.
The induced subgraph G[W] keeps the vertices in W and every edge of G between them.
G − v deletes a vertex and its incident edges. G − e deletes an edge only. G + e adds an edge.
The union G₁ ∪ G₂ has vertex set V₁ ∪ V₂ and edge set E₁ ∪ E₂.
The complement Ḡ has the same vertices as G, and {u, v} is an edge of Ḡ exactly when it is not an edge of G (for u ≠ v).

Since every pair of distinct vertices is an edge of exactly one of G and Ḡ,

  m(G) + m(Ḡ) = C(n, 2)        and        deg_Ḡ(v) = n − 1 − deg_G(v)

A graph isomorphic (8.2) to its own complement is self-complementary. P₄ and C₅ are the smallest examples: the complement of a pentagon is a pentagram, which is another 5-cycle.

   G = C₅ (pentagon)          Ḡ (pentagram, redrawn as a cycle)
          0                            0
        ╱   ╲                        ╱   ╲
       4     1                      3     2
        ╲   ╱                        ╲   ╱
         3 ─ 2                        1 ─ 4

   edges of Ḡ: {0,2}, {0,3}, {1,3}, {1,4}, {2,4}   =   the 5-cycle 0-2-4-1-3-0

from itertools import combinations

def complement(vertices, edges):
    E = {frozenset(e) for e in edges}
    return [p for p in combinations(sorted(vertices), 2) if frozenset(p) not in E]

def induced(edges, W):
    return [(u, v) for u, v in edges if u in W and v in W]

C5 = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
print(complement(range(5), C5))                 # [(0, 2), (0, 3), (1, 3), (1, 4), (2, 4)]
print(induced(C5, {0, 1, 2}))                   # [(0, 1), (1, 2)]   a path, not a triangle

K4 = list(combinations(range(4), 2))
print(len(K4) + len(complement(range(4), K4)))  # 6 = C(4, 2): the complement of K4 has no edges

Key takeaways

A subgraph takes some vertices and some of the edges among them. An induced subgraph takes all edges among the chosen vertices.
A spanning subgraph keeps every vertex.
The complement swaps edges and non-edges: m(G) + m(Ḡ) = C(n, 2).
Cliques in G are independent sets in Ḡ.

Practice

(Beginner) How many subgraphs does K₃ have (count subgraphs on every non-empty vertex subset)? How many of them are induced?

(Intermediate) Prove that a self-complementary graph on n vertices has n ≡ 0 or n ≡ 1 (mod 4). Hint: G and Ḡ have the same number of edges, so m = n(n − 1)/4 must be an integer.

(Interview) Prove that among any 6 people there are either 3 mutual friends or 3 mutual strangers, so that every graph on 6 vertices contains a triangle in G or in Ḡ. Hint: fix one person. Of the 5 others, at least 3 are friends or at least 3 are strangers (pigeonhole, 5.4). Look at the edges among those 3.

8.2 Graph Representation and Isomorphism

Adjacency Lists

     a ─────── b             a: [b, c]
     │       ╱               b: [a, c]
     │     ╱                 c: [a, b, d]
     │   ╱                   d: [c]
     c ─────── d             e: []           total entries: 2m = 8
                e

The total size is n lists plus 2m entries (m entries for a digraph), so the space is Θ(n + m).

Operation	Cost with adjacency lists
Space	`Θ(n + m)`
Iterate over the neighbors of `v`	`Θ(deg v)`, optimal
Test whether `{u, v}` is an edge	`O(deg u)` with lists, expected `O(1)` with hash sets
Iterate over all edges	`Θ(n + m)`
Add an edge	`O(1)`
Remove an edge	`O(deg u + deg v)` with lists, expected `O(1)` with hash sets

Variants.

Dictionary of sets (dict[vertex, set]): vertices can be any hashable value, and edge tests take expected O(1) time. This is the usual choice in Python.
Arrays of arrays: vertices are numbered 0, …, n − 1, and each list is a dynamic array. This is the standard choice in competitive programming and in Java (List<List<Integer>>).
Compressed sparse row (CSR): all lists are concatenated into one array targets, and offsets[v] marks where the list of v starts. It uses two flat arrays and no per-list overhead, which makes it compact and cache-friendly. Graph-processing libraries use it for graphs with billions of edges, at the price of being expensive to modify.

from collections import defaultdict

def adjacency_list(edges, directed=False):
    adj = defaultdict(set)
    for u, v in edges:
        adj[u].add(v)
        if not directed:
            adj[v].add(u)                            # undirected: store both directions
    return adj

adj = adjacency_list([("a", "b"), ("a", "c"), ("b", "c"), ("c", "d")])
adj["e"]                                             # touching a defaultdict key adds the isolated vertex e
print({v: sorted(ns) for v, ns in sorted(adj.items())})
# {'a': ['b', 'c'], 'b': ['a', 'c'], 'c': ['a', 'b', 'd'], 'd': ['c'], 'e': []}
print("d" in adj["c"], sum(len(ns) for ns in adj.values()))   # True 8   (= 2m)

def to_csr(n, arcs):
    """Directed graph on 0..n-1 as two flat arrays: offsets (n + 1 entries) and targets (m entries)."""
    offsets = [0] * (n + 1)
    for u, _ in arcs:
        offsets[u + 1] += 1                          # count the out-degree of each vertex
    for i in range(n):
        offsets[i + 1] += offsets[i]                 # prefix sums: where each list starts
    targets, fill = [0] * len(arcs), offsets[:-1]    # slicing makes fill a copy of the starts
    for u, v in arcs:
        targets[fill[u]] = v
        fill[u] += 1
    return offsets, targets

offsets, targets = to_csr(4, [(0, 1), (0, 2), (2, 3), (1, 2), (3, 0)])
print(offsets, targets)                              # [0, 2, 3, 4, 5] [1, 2, 2, 3, 0]
print(targets[offsets[0]:offsets[1]])                # [1, 2]   out-neighbors of vertex 0

Key takeaways

An adjacency list stores each vertex's neighbors and uses Θ(n + m) space, which suits sparse graphs.
Iterating over neighbors costs Θ(deg v), which is what traversal algorithms (8.4) need.
Use hash sets when you also need fast edge tests, and CSR arrays for very large static graphs.
In an undirected graph, every edge is stored twice.

Practice

(Beginner) Write the adjacency list of W₄ (rim 1, 2, 3, 4, hub h). How many entries does it contain in total?

(Intermediate) Given the adjacency list of a directed graph, build the adjacency list of its reverse (every arc flipped) in O(n + m) time. Then use it to list all vertices with in-degree 0.

(Interview) A road network has 50 million intersections and 120 million road segments, and the graph never changes once loaded. Estimate the memory for CSR with 4-byte integers, and compare it with a dictionary of sets in Python. Hint: CSR needs n + 1 offsets plus 2m targets for undirected edges. A Python object costs tens of bytes.

Adjacency Matrices

What. Number the vertices v₁, …, vₙ. The adjacency matrix is the n × n matrix A with

  aᵢⱼ = 1   if {vᵢ, vⱼ} is an edge
  aᵢⱼ = 0   otherwise

     1 ─── 2              1  2  3  4
     │     │          1 [ 0  1  0  1 ]
     │     │          2 [ 1  0  1  0 ]       C₄
     4 ─── 3          3 [ 0  1  0  1 ]
                      4 [ 1  0  1  0 ]

Properties:

An undirected graph has a symmetric matrix. A simple graph has zeros on the diagonal.
The sum of row i is deg(vᵢ). For a digraph, row sums are out-degrees and column sums are in-degrees.
Relabeling the vertices permutes the rows and columns in the same way.

Walks and matrix powers. A walk of length k is a sequence of k edges where each edge starts where the previous one ended (8.3).

Theorem. (Aᵏ)ᵢⱼ is the number of walks of length k from vᵢ to vⱼ.

Two consequences:

(A²)ᵢᵢ = deg(vᵢ), because a closed walk of length 2 goes out along an edge and comes straight back.
A triangle gives 6 closed walks of length 3 (3 starting vertices times 2 directions), so the number of triangles is trace(A³)/6.

	Adjacency list	Adjacency matrix
Space	`Θ(n + m)`	`Θ(n²)`
Edge test `{u, v}`	`O(deg u)` or expected `O(1)` with hashing	`O(1)`
Iterate over neighbors of `v`	`Θ(deg v)`	`Θ(n)`
Iterate over all edges	`Θ(n + m)`	`Θ(n²)`
Add or remove an edge	`O(1)` to `O(deg)`	`O(1)`
Best for	Sparse graphs, traversals	Dense graphs, frequent edge tests, linear algebra

As a rule of thumb, use a matrix when m is a constant fraction of n², or when n is small (a few thousand vertices at most). One million vertices would need 10¹² entries.

def matmul(X, Y):
    return [[sum(X[i][k] * Y[k][j] for k in range(len(Y))) for j in range(len(Y[0]))]
            for i in range(len(X))]

def adjacency_matrix(n, edges):
    A = [[0] * n for _ in range(n)]
    for u, v in edges:
        A[u][v] = A[v][u] = 1                        # undirected: symmetric
    return A

C4 = adjacency_matrix(4, [(0, 1), (1, 2), (2, 3), (3, 0)])
A2 = matmul(C4, C4)
print(A2)            # [[2, 0, 2, 0], [0, 2, 0, 2], [2, 0, 2, 0], [0, 2, 0, 2]]
# Diagonal = degrees. Two walks of length 2 from vertex 0 to vertex 2 (via 1 or via 3).

K4 = adjacency_matrix(4, [(i, j) for i in range(4) for j in range(i + 1, 4)])
A3 = matmul(matmul(K4, K4), K4)
print(sum(A3[i][i] for i in range(4)) // 6)        # 4   triangles in K4: trace(A^3) / 6

Key takeaways

aᵢⱼ = 1 when vᵢ and vⱼ are adjacent. An undirected graph has a symmetric matrix, and the row sums are the degrees.
Θ(n²) space and O(1) edge tests: use a matrix for small or dense graphs.
(Aᵏ)ᵢⱼ counts walks of length k from vᵢ to vⱼ, and trace(A³)/6 counts triangles.
Relabeling vertices permutes the rows and columns of A simultaneously.

Practice

(Beginner) Write the adjacency matrix of K_{1,3} with the center listed first. Compute A² and interpret its entries.

(Intermediate) Prove that a graph is bipartite with parts {v₁, …, vₖ} and {vₖ₊₁, …, vₙ} exactly when its adjacency matrix has the block form [[0, B], [Bᵀ, 0]]. Use this to show that (Aᵏ)ᵢᵢ = 0 for every odd k in a bipartite graph.

(Interview) You must count triangles in a social graph with 10⁸ vertices and 10¹⁰ edges. Why is computing trace(A³) with dense matrices hopeless, and what would you do instead? Hint: for each edge {u, v}, intersect the neighbor sets of u and v. Orienting each edge from lower to higher degree keeps the sets small.

Incidence Matrices

What. Number the vertices v₁, …, vₙ and the edges e₁, …, eₘ. The incidence matrix is the n × m matrix M with

  mᵢⱼ = 1   if edge eⱼ is incident to vertex vᵢ
  mᵢⱼ = 0   otherwise

  B · Bᵀ = D − A = L

where D is the diagonal matrix of degrees. L is the Laplacian matrix. It does not depend on the orientation chosen, and Kirchhoff's matrix-tree theorem uses it to count spanning trees (9.4).

                       e₁  e₂  e₃  e₄
     a ──e₁── b     a [ 1   1   0   0 ]      e₁ = {a, b}
     │       ╱      b [ 1   0   1   0 ]      e₂ = {a, c}
    e₂    e₃        c [ 0   1   1   1 ]      e₃ = {b, c}
     │   ╱          d [ 0   0   0   1 ]      e₄ = {c, d}
     c ──e₄── d

V = ["a", "b", "c", "d"]
E = [("a", "b"), ("a", "c"), ("b", "c"), ("c", "d")]

M = [[1 if v in e else 0 for e in E] for v in V]
print([sum(row) for row in M])                      # [2, 2, 3, 1]   row sums are degrees
print([sum(col) for col in zip(*M)])                # [2, 2, 2, 2]   every edge has two ends

# Oriented incidence matrix: -1 at the tail, +1 at the head (orientation chosen as listed)
B = [[-1 if v == e[0] else 1 if v == e[1] else 0 for e in E] for v in V]
L = [[sum(B[i][k] * B[j][k] for k in range(len(E))) for j in range(len(V))] for i in range(len(V))]
for row in L:
    print(row)
# [2, -1, -1, 0]
# [-1, 2, -1, 0]
# [-1, -1, 3, -1]
# [0, 0, -1, 1]      L = D - A: degrees on the diagonal, -1 for each edge

Key takeaways

The incidence matrix is n × m, with a 1 where a vertex meets an edge.
Each column has two 1s and each row sums to the degree, which is the handshaking lemma in matrix form.
The oriented version has −1 and +1 in each column, and B · Bᵀ is the Laplacian D − A.
It uses Θ(nm) space, so it is a tool for theory and linear algebra rather than a general-purpose data structure.

Practice

(Beginner) Write the incidence matrix of C₄ with edges e₁ = {1, 2}, e₂ = {2, 3}, e₃ = {3, 4}, e₄ = {4, 1}.

(Intermediate) Show that the rows of an oriented incidence matrix sum to the zero vector, so its rank is at most n − 1. Show also that every row sum of the Laplacian L is 0.

(Interview) In a flow network (8.6), let f be the vector of flows on the arcs and B the oriented incidence matrix. What does the vector B · f represent, and how would you state "flow is conserved at every vertex except the source and the sink" as a linear constraint? Hint: entry i of B · f is the flow into vᵢ minus the flow out of it.

Graph Isomorphism

What. Graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) are isomorphic, written G₁ ≅ G₂, if there is a bijection f : V₁ → V₂ (2.2) such that

  {u, v} ∈ E₁   ⟺   {f(u), f(v)} ∈ E₂        for all u, v ∈ V₁

In matrix terms, G₁ ≅ G₂ exactly when A₂ = P · A₁ · Pᵀ for some permutation matrix P: relabeling permutes rows and columns together.

Example. Both drawings below show the same 4-cycle.

     G₁                 G₂
   1 ──── 2           a      b
   │      │           │ ╲  ╱ │         f(1) = a,  f(2) = c,  f(3) = b,  f(4) = d
   │      │           │  ╳   │         {1,2} ↦ {a,c}   {2,3} ↦ {c,b}
   4 ──── 3           │ ╱  ╲ │         {3,4} ↦ {b,d}   {4,1} ↦ {d,a}
                      c      d

How.

To prove G₁ ≅ G₂, give an explicit bijection and check every edge.
To disprove it, find a property that every isomorphism preserves but the two graphs do not share (the next topic, Graph Invariants).

from itertools import permutations

def find_isomorphism(n, E1, E2):
    """Brute force over bijections of {0, ..., n-1}, pruned by degrees."""
    A = {frozenset(e) for e in E1}
    B = {frozenset(e) for e in E2}
    if len(A) != len(B):
        return None
    deg1 = [sum(v in e for e in A) for v in range(n)]
    deg2 = [sum(v in e for e in B) for v in range(n)]
    for f in permutations(range(n)):
        if any(deg1[v] != deg2[f[v]] for v in range(n)):
            continue                                 # degrees must be preserved
        # f maps edges injectively into B and |A| = |B|, so non-edges also map to non-edges
        if all(frozenset(f[v] for v in e) in B for e in A):
            return dict(enumerate(f))
    return None

pentagon  = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
pentagram = [(0, 2), (2, 4), (4, 1), (1, 3), (3, 0)]
print(find_isomorphism(5, pentagon, pentagram))     # {0: 0, 1: 2, 2: 4, 3: 1, 4: 3}

path_P4 = [(0, 1), (1, 2), (2, 3)]
star    = [(0, 1), (0, 2), (0, 3)]
print(find_isomorphism(4, path_P4, star))           # None   degrees (1, 2, 2, 1) vs (3, 1, 1, 1)

Key takeaways

An isomorphism is a bijection of vertices that preserves adjacency and non-adjacency.
Isomorphic graphs are the same graph with different names. The drawing is irrelevant.
Prove isomorphism with an explicit bijection. Disprove it with an invariant.
No polynomial-time algorithm is known, but canonical labeling is fast in practice.

Practice

(Beginner) Show that C₅ is isomorphic to its complement by writing out the bijection and checking all five edges.

(Intermediate) There are 11 non-isomorphic simple graphs on 4 vertices. Draw them, grouping by the number of edges (0 to 6). Hint: the counts by number of edges are 1, 1, 2, 3, 2, 1, 1. Complementation pairs up k edges with 6 − k.

(Interview) A chemistry database stores millions of molecules as graphs and must reject duplicates on insert. Hashing the edge list fails because the same molecule can be numbered differently. How would you design the duplicate check? Hint: compute a cheap invariant hash (such as refined degree colors, next topic) to find candidates, then confirm with an exact isomorphism test or a canonical form.

Graph Invariants

Invariant	Cost to compute	Notes
Number of vertices, number of edges	`O(1)`	The first check
Degree sequence	`O(n + m)`	Very effective in practice
Number of connected components (8.3)	`O(n + m)`
Bipartite or not (8.1)	`O(n + m)`	Presence of odd cycles
Number of triangles, or of `k`-cycles for fixed `k`	Polynomial
Distances: diameter, girth (8.3)	Polynomial
Spectrum (eigenvalues of `A`)	Polynomial	Different graphs can share it (cospectral graphs)
Planarity (8.5)	`O(n)`
Chromatic number (8.5)	NP-hard

        C₆                   2K₃
      1 ── 2               1       4
    ╱        ╲            ╱ ╲     ╱ ╲
   6          3          2 ─ 3   5 ─ 6
    ╲        ╱
      5 ── 4             degree sequence (2, 2, 2, 2, 2, 2) in both graphs

from collections import Counter

def wl_histograms(adj1, adj2, rounds=3):
    """Color refinement on two graphs with a shared palette, so that colors are comparable."""
    graphs = [adj1, adj2]
    colors = [{v: 0 for v in g} for g in graphs]
    for _ in range(rounds):
        sigs = [{v: (c[v], tuple(sorted(c[w] for w in g[v]))) for v in g}   # own color + neighbors' colors
                for g, c in zip(graphs, colors)]
        palette = {s: i for i, s in enumerate(sorted(set(sigs[0].values()) | set(sigs[1].values())))}
        colors = [{v: palette[s[v]] for v in s} for s in sigs]
    return [sorted(Counter(c.values()).items()) for c in colors]

def adj_from(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, []).append(v)
        adj.setdefault(v, []).append(u)
    return adj

def triangles(adj):
    return sum(len(set(adj[u]) & set(adj[v])) for u in adj for v in adj[u]) // 6

H1 = adj_from([(0, 1), (1, 2), (2, 0), (2, 3), (3, 4)])            # triangle with a tail
H2 = adj_from([(0, 1), (1, 2), (2, 3), (3, 0), (3, 4)])            # square with a tail
print(sorted(len(a) for a in H1.values()) == sorted(len(a) for a in H2.values()))   # True   same degrees
h1, h2 = wl_histograms(H1, H2)
print(h1 == h2)                                                    # False  refinement tells them apart

C6  = adj_from([(i, (i + 1) % 6) for i in range(6)])
twoK3 = adj_from([(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3)]) # two disjoint triangles
h1, h2 = wl_histograms(C6, twoK3)
print(h1 == h2, triangles(C6), triangles(twoK3))                   # True 0 2   refinement fails, triangles succeed

Key takeaways

An invariant is preserved by every isomorphism. Different values prove non-isomorphism, and equal values prove nothing.
Check cheap invariants first: n, m, the degree sequence, components, bipartiteness, triangles.
C₆ and 2K₃ have the same degree sequence but are not isomorphic.
Color refinement (1-WL) is a fast, strong invariant, but it cannot separate regular graphs with the same degree and size.

Practice

(Beginner) Prove that K_{3,3} and the triangular prism (two triangles a₁a₂a₃ and b₁b₂b₃ plus the edges aᵢbᵢ) are not isomorphic, although both are 3-regular with 6 vertices.

(Intermediate) Find two connected, non-isomorphic graphs with the same degree sequence, and name an invariant that distinguishes them. Hint: start from H1 and H2 above, or try 6 vertices with one graph bipartite and the other not.

(Interview) A colleague proposes using (n, m, sorted degree sequence) as a dictionary key to group "identical" network topologies. When does this give wrong answers, and how would you make the grouping exact while keeping it fast? Hint: the key is an invariant, not a complete one, so equal keys only make two graphs candidates. Refine the key, then confirm each group with an isomorphism test.

8.3 Connectivity

Walks, Paths, and Cycles

Name	Repeated vertices?	Repeated edges?	Closed?
Walk	Allowed	Allowed	Either
Trail	Allowed	No	Either
Path	No	No	No
Closed walk	Allowed	Allowed	Yes
Circuit (closed trail)	Allowed	No	Yes
Cycle	No, except `v₀ = vₖ`	No	Yes, with length `≥ 3`

Terminology varies between textbooks. Some (Rosen, for example) say "path" for what this table calls a walk and "simple path" for a path. Always check the definitions in use.

Lemma 1. Every walk from u to v contains a path from u to v.

Lemma 2. Every closed walk of odd length contains a cycle of odd length.

   a ─── b ─── c
   │     │     │          a, b, e, d, a, b, c   walk (edge {a, b} used twice)
   │     │     │          a, b, c, f, e, b      trail (b visited twice, no edge repeated)
   d ─── e ─── f          a, b, c, f, e         path
                          a, b, e, d, a         cycle of length 4 (the girth)
                          diameter = d(a, f) = d(d, c) = 3

adj = {"a": "bd", "b": "ace", "c": "bf", "d": "ae", "e": "bdf", "f": "ce"}

def classify(seq):
    steps = list(zip(seq, seq[1:]))
    if any(w not in adj[v] for v, w in steps):
        return "not a walk"
    closed = len(seq) > 1 and seq[0] == seq[-1]
    edges = [frozenset(s) for s in steps]
    if len(set(edges)) < len(edges):
        return "closed walk" if closed else "walk"
    inner = seq[:-1] if closed else seq                # the endpoints of a closed walk coincide
    if len(set(inner)) < len(inner):
        return "circuit" if closed else "trail"
    return "cycle" if closed else "path"

for s in ["abedabc", "abcfeb", "abcfe", "abeda", "abcfedeba", "ac"]:
    print(s, classify(s))
# abedabc walk
# abcfeb trail
# abcfe path
# abeda cycle
# abcfedeba closed walk
# ac not a walk

def walk_to_path(walk):
    """Lemma 1 as code: cut out the loop each time a vertex repeats."""
    path, pos = [], {}
    for v in walk:
        if v in pos:
            for w in path[pos[v] + 1:]:
                del pos[w]                              # forget the vertices on the removed loop
            path = path[:pos[v] + 1]
        else:
            pos[v] = len(path)
            path.append(v)
    return "".join(path)

print(walk_to_path("abedabc"))                        # abc

Key takeaways

Walk: anything goes. Trail: no repeated edges. Path: no repeated vertices. Cycle: a closed path of length at least 3.
The length of a walk is its number of edges.
Every u–v walk contains a u–v path, so "reachable by a walk" and "reachable by a path" mean the same thing.
Every odd closed walk contains an odd cycle.
d(u, v) is the length of a shortest path. The diameter is the largest distance and the girth the shortest cycle length.

Practice

(Beginner) In the grid graph above, find a trail from a to f that is not a path, a circuit that is not a cycle (if one exists), and every cycle through a.

(Intermediate) Prove that if every vertex of a graph has degree at least 2, the graph contains a cycle. Hint: consider a longest path v₀, …, vₖ. Where can the other neighbors of vₖ be?

(Interview) A function receives a sequence of node IDs that is supposed to be a route in a network, and must report whether it is a valid walk, a trail, or a path. Write it to run in O(k) time for a route of length k. Hint: store the adjacency lists as hash sets, and track visited vertices and used edges (as unordered pairs) in hash sets.

Connected Components

What. Write u ~ v if there is a walk (equivalently, by Lemma 1, a path) from u to v. This is an equivalence relation (2.5):

Reflexive: the walk of length 0 goes from v to v.
Symmetric: reverse the walk.
Transitive: join a u–v walk and a v–w walk.

   1 ─── 2         4 ─── 5         6 ─── 7
         │                          ╲   ╱
         3                            8

   three components: {1, 2, 3}, {4, 5}, {6, 7, 8}

Facts.

Adding one edge reduces the number of components by at most 1. Starting from n isolated vertices, you therefore need at least n − k edges to end with k components. In particular, a connected graph has m ≥ n − 1 edges, with equality exactly for trees (9.1).
If G is disconnected, its complement Ḡ is connected.

How.

Traversal. Run BFS or DFS (8.4) from an unvisited vertex, label everything it reaches, and repeat. This takes O(n + m) time.
Union–find (disjoint-set forest). Start with every vertex in its own set and, for each edge, merge the sets of its endpoints. This handles edges that arrive one at a time and answers "are u and v connected?" at any moment. With path compression and union by size, each operation takes amortized O(α(n)) time, where α is the inverse Ackermann function, which is at most 4 for any practical n. Kruskal's algorithm (9.4) uses this structure.

class DisjointSets:
    def __init__(self, items):
        self.parent = {x: x for x in items}
        self.size = {x: 1 for x in items}

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:                 # path compression: point straight at the root
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                              # already in the same component
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                           # union by size: hang the smaller tree
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

ds = DisjointSets(range(1, 9))
for u, v in [(1, 2), (2, 3), (4, 5), (6, 7), (7, 8), (8, 6)]:
    ds.union(u, v)

groups = {}
for v in range(1, 9):
    groups.setdefault(ds.find(v), []).append(v)
print(list(groups.values()))                          # [[1, 2, 3], [4, 5], [6, 7, 8]]
print(ds.find(3) == ds.find(5))                       # False
ds.union(3, 4)                                        # a new edge joins two components
print(ds.find(1) == ds.find(5))                       # True

Key takeaways

"There is a path from u to v" is an equivalence relation, and its classes are the connected components.
A connected graph on n vertices has at least n − 1 edges.
Find components with BFS or DFS in O(n + m), or with union–find when edges arrive incrementally.
The complement of a disconnected graph is connected.

Practice

(Beginner) How many components does the graph on {1, …, 12} have, where i and j are adjacent when |i − j| = 4?

(Intermediate) Prove that if G is disconnected, then Ḡ is connected. Hint: take u and v. If they lie in different components of G, they are adjacent in Ḡ. If they lie in the same component, find a vertex w in another component.

(Interview) Given a grid of '1' (land) and '0' (water), count the islands, where land cells are connected horizontally and vertically. Then handle a stream of "turn cell (r, c) into land" updates, reporting the island count after each one. Hint: the grid is an implicit graph. For the stream, use union–find: each new land cell adds one component and each successful union removes one.

Strongly Connected Components

    a ───► b
    ▲     ╱
    │   ╱
    │  ▼
    c ───► d ◄──► e ───► f ◄─── g

   arcs: a→b, b→c, c→a, c→d, d→e, e→d, e→f, g→f

   condensation:   {a, b, c} ───► {d, e} ───► {f} ◄─── {g}

How. Two classic algorithms find all SCCs in O(n + m) time.

Kosaraju's algorithm. (1) Run DFS (8.4) on the graph and record vertices in order of finishing. (2) Reverse every arc. (3) Take vertices in decreasing finishing time and run a DFS from each unvisited one in the reversed graph. Each such DFS visits exactly one SCC. It works because the vertex that finishes last lies in a source SCC of the condensation. In the reversed graph that SCC becomes a sink, so a search from it cannot leak into other components.
Tarjan's algorithm does it in one DFS pass, using the low-link values described in the next topic.

def strongly_connected_components(adj):
    """Kosaraju's algorithm with explicit stacks (no recursion limit)."""
    order, seen = [], set()
    for s in adj:                                     # pass 1: record finishing order
        if s in seen:
            continue
        seen.add(s)
        stack = [(s, iter(adj[s]))]
        while stack:
            v, it = stack[-1]
            for w in it:
                if w not in seen:
                    seen.add(w)
                    stack.append((w, iter(adj[w])))
                    break
            else:
                stack.pop()
                order.append(v)                       # v is finished: all its descendants are done

    rev = {v: [] for v in adj}
    for v in adj:
        for w in adj[v]:
            rev[w].append(v)

    comp = {}
    for s in reversed(order):                         # pass 2: decreasing finishing time, reversed arcs
        if s in comp:
            continue
        comp[s] = s
        stack = [s]
        while stack:
            v = stack.pop()
            for w in rev[v]:
                if w not in comp:
                    comp[w] = s
                    stack.append(w)
    return comp                                        # vertex -> representative of its SCC

adj = {"a": ["b"], "b": ["c"], "c": ["a", "d"], "d": ["e"], "e": ["d", "f"], "f": [], "g": ["f"]}
comp = strongly_connected_components(adj)
sccs = {}
for v, r in comp.items():
    sccs.setdefault(r, []).append(v)
print(sorted(sorted(c) for c in sccs.values()))       # [['a', 'b', 'c'], ['d', 'e'], ['f'], ['g']]

dag = sorted({(comp[v], comp[w]) for v in adj for w in adj[v] if comp[v] != comp[w]})
print(dag)                                            # [('a', 'd'), ('d', 'f'), ('g', 'f')]   condensation arcs

Key takeaways

Strongly connected: every vertex reaches every other along directed paths. Weakly connected: connected when directions are ignored.
SCCs are the classes of mutual reachability, and every directed graph splits into them.
The condensation (one vertex per SCC) is always a DAG.
Kosaraju (two DFS passes, one on the reversed graph) and Tarjan (one pass) both run in O(n + m).

Practice

(Beginner) Find the SCCs of the digraph with arcs 1→2, 2→3, 3→1, 3→4, 4→5, 5→6, 6→4, 6→7. Draw its condensation.

(Intermediate) Prove that the condensation of any directed graph is acyclic. Then show that a strongly connected digraph on n ≥ 2 vertices has at least n arcs.

(Interview) A microservice platform records "service X calls service Y" as arcs. Engineers want to find every group of services that are mutually dependent (and so must be deployed together), and an order in which to deploy the groups. Hint: the groups are the SCCs, and a deployment order is a reverse topological order of the condensation. Both come out of a single run of Tarjan's or Kosaraju's algorithm.

Cut Vertices and Bridges

What. In a connected graph:

A cut vertex (articulation point) is a vertex whose removal, together with its incident edges, disconnects the graph. In general, a cut vertex is one whose removal increases the number of components.
A bridge (cut edge) is an edge whose removal increases the number of components.

A graph with at least 3 vertices and no cut vertex is biconnected (2-connected).

Characterizations.

An edge is a bridge if and only if it lies on no cycle. (A cycle gives a detour around the edge, and a detour together with the edge forms a cycle.)
Every edge of a tree is a bridge, and every non-leaf vertex of a tree is a cut vertex (9.1).
If {u, v} is a bridge and deg(u) ≥ 2, then u is a cut vertex.

     a               e
     │ ╲           ╱ │
     │   c ───── d   │          bridges:      {c, d}, {f, g}
     │ ╱           ╲ │          cut vertices: c, d, f
     b               f ───── g

Condition	Conclusion	Reason
`low[w] > disc[u]`	`{u, w}` is a bridge	Nothing below `w` can reach `u` or above without this edge
`low[w] ≥ disc[u]`, `u` not the root	`u` is a cut vertex	Removing `u` cuts off `w`'s subtree
`u` is the root with `≥ 2` DFS children	`u` is a cut vertex	In an undirected DFS, different subtrees of the root are not joined by any edge

The whole computation is one DFS, so it takes O(n + m) time.

def cut_vertices_and_bridges(adj):
    """Hopcroft–Tarjan low-link DFS for a simple undirected graph."""
    disc, low, cuts, bridges = {}, {}, set(), []
    timer = 0

    def dfs(u, parent):
        nonlocal timer
        disc[u] = low[u] = timer
        timer += 1
        children = 0
        for w in adj[u]:
            if w not in disc:                             # tree edge u -> w
                children += 1
                dfs(w, u)
                low[u] = min(low[u], low[w])
                if low[w] > disc[u]:
                    bridges.append((u, w))                # w's subtree can't get around this edge
                if parent is not None and low[w] >= disc[u]:
                    cuts.add(u)                           # w's subtree can't get around u
            elif w != parent:
                low[u] = min(low[u], disc[w])             # back edge to an ancestor
        if parent is None and children >= 2:
            cuts.add(u)

    for v in adj:                                         # recursion depth ~ n: fine for small graphs
        if v not in disc:
            dfs(v, None)
    return sorted(cuts), bridges

adj = {"a": "bc", "b": "ac", "c": "abd", "d": "cef", "e": "df", "f": "deg", "g": "f"}
print(cut_vertices_and_bridges(adj))                      # (['c', 'd', 'f'], [('f', 'g'), ('c', 'd')])

Key takeaways

Cut vertices and bridges are single points of failure: removing one disconnects the graph.
An edge is a bridge exactly when it lies on no cycle.
One DFS with disc and low values finds all of them in O(n + m): low[w] > disc[u] gives a bridge, and low[w] ≥ disc[u] gives a cut vertex (with a special rule for the root).
A biconnected graph has no cut vertex.

Practice

(Beginner) Find all cut vertices and bridges of the path P₅, the cycle C₅, the star K_{1,4}, and two copies of K₄ sharing one vertex.

(Intermediate) Prove that an edge is a bridge if and only if it lies on no cycle. Then explain why a vertex of degree 1 is never a cut vertex.

(Interview) Given n servers and a list of network links, return every "critical connection", that is, every link whose failure disconnects some servers from others. Your solution must handle 10⁵ servers and links. Hint: this is the bridge-finding DFS. At that size, Python's recursion limit forces an iterative version with an explicit stack. Process a child's low value when the child is popped.

Vertex and Edge Connectivity

What.

A vertex cut is a set of vertices whose removal disconnects the graph. The vertex connectivity κ(G) is the size of a smallest vertex cut. For the complete graph, which has no vertex cut, κ(Kₙ) = n − 1 by convention.
An edge cut is a set of edges whose removal disconnects the graph. The edge connectivity λ(G) is the size of a smallest edge cut.
G is k-connected if κ(G) ≥ k, and k-edge-connected if λ(G) ≥ k. A disconnected graph has κ = λ = 0.

Whitney's inequality. For every graph,

  κ(G) ≤ λ(G) ≤ δ(G)

The second inequality is easy: removing all δ edges at a vertex of minimum degree isolates it. The first is proved by removing one well-chosen endpoint of each edge in a minimum edge cut.

Graph	`κ`	`λ`	`δ`
`Kₙ`	`n − 1`	`n − 1`	`n − 1`
`Cₙ`	2	2	2
`Wₙ`	3	3	3
`Qₙ`	`n`	`n`	`n`
`K_{m,n}`, `m ≤ n`	`m`	`m`	`m`
Tree with `n ≥ 3` vertices	1	1	1

The inequalities can all be strict. Take two copies of K₄ and join one vertex a of the first to two vertices w, x of the second:

     b ─── c                 y ─── z
     │ ╲ ╱ │                 │ ╲ ╱ │          κ = 1  (remove a)
     │  ╳  │                 │  ╳  │          λ = 2  (remove {a, w} and {a, x})
     d ─── a ─────────────── w ─── x          δ = 3  (b, c, d, y, z have degree 3)
            ╲                     ╱
             ╰───────────────────╯

(Each K₄ has all six of its edges, and a is joined to both w and x.)

from itertools import combinations

def connected(vertices, edges):
    vertices = set(vertices)
    if len(vertices) <= 1:
        return True
    adj = {v: set() for v in vertices}
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    start = next(iter(vertices))
    seen, stack = {start}, [start]
    while stack:
        for w in adj[stack.pop()] - seen:
            seen.add(w)
            stack.append(w)
    return seen == vertices

def kappa(V, E):                                   # brute force: try vertex sets by increasing size
    for k in range(len(V) - 1):
        for S in combinations(V, k):
            rest = [v for v in V if v not in S]
            if not connected(rest, [e for e in E if e[0] not in S and e[1] not in S]):
                return k
    return len(V) - 1                              # no vertex cut: complete graph

def lam(V, E):                                     # brute force: try edge sets by increasing size
    for k in range(len(E) + 1):
        for F in combinations(E, k):
            if not connected(V, [e for e in E if e not in F]):
                return k

V = list("abcdwxyz")
E = list(combinations("abcd", 2)) + list(combinations("wxyz", 2)) + [("a", "w"), ("a", "x")]
delta = min(sum(v in e for e in E) for v in V)
print(kappa(V, E), lam(V, E), delta)               # 1 2 3

Q3 = [(u, u ^ b) for u in range(8) for b in (1, 2, 4) if u < u ^ b]
print(kappa(range(8), Q3), lam(range(8), Q3))      # 3 3

Key takeaways

κ(G) is the fewest vertices, and λ(G) the fewest edges, whose removal disconnects G.
Whitney: κ ≤ λ ≤ δ, and each inequality can be strict.
Menger: the size of a minimum separating set equals the maximum number of disjoint paths, in both the vertex and the edge version.
k-connectivity is the standard measure of fault tolerance, and max-flow algorithms (8.6) compute it.

Practice

(Beginner) Compute κ, λ and δ for K_{2,4}, W₆, and the graph made of two triangles sharing one vertex.

(Intermediate) Prove λ(G) ≤ δ(G). Then give a graph with κ(G) = 1 and λ(G) = 5. Hint: glue two large complete graphs at a single vertex.

(Interview) You are designing links between n data centers so that the network stays connected after any 2 link failures, using as few links as possible. What is the lower bound on the number of links, and what topology achieves it? Hint: 3-edge-connected implies δ ≥ 3, so the handshaking lemma gives m ≥ 3n/2. For even n, consider a cycle plus "diameter" chords joining opposite vertices.

8.4 Traversals and Paths

Breadth-First Search

dist[v]: the number of edges on a shortest path from s to v, and
parent[v]: the vertex from which v was discovered. The parent pointers form a BFS tree, and following them back from v gives a shortest path.

Analogy. Drop a stone in a pond. The ripple reaches every point at distance 1 before any point at distance 2. BFS is the ripple, and the queue holds the current wavefront.

How.

Set dist[s] = 0 and put s in the queue.
Remove the vertex u at the front of the queue. For each neighbor w that has not been discovered yet, set dist[w] = dist[u] + 1 and parent[w] = u, and add w to the back of the queue.
Repeat until the queue is empty.

Mark a vertex as discovered when it enters the queue, not when it leaves. Otherwise a vertex can be queued many times.

Every vertex enters the queue at most once, and every adjacency list is scanned once, so BFS runs in O(n + m) time with adjacency lists (O(n²) with a matrix).

            s                    layer 0:  s
          ╱   ╲                  layer 1:  a, b
         a     b                 layer 2:  c, d, e
         │ ╲   │                 layer 3:  t
         c   d ─ e
          ╲ ╱                    shortest s–t path: s, a, c, t   (length 3)
           t

from collections import deque

def bfs(adj, s):
    dist, parent = {s: 0}, {s: None}
    queue = deque([s])
    while queue:
        u = queue.popleft()                          # FIFO: closest undiscovered layer first
        for w in adj[u]:
            if w not in dist:                        # mark on enqueue, so each vertex is queued once
                dist[w] = dist[u] + 1
                parent[w] = u
                queue.append(w)
    return dist, parent

def path_to(parent, t):
    path = []
    while t is not None:
        path.append(t)
        t = parent[t]
    return path[::-1]

adj = {"s": "ab", "a": "scd", "b": "se", "c": "at", "d": "aet", "e": "bd", "t": "cd"}
dist, parent = bfs(adj, "s")
print(dist)                                          # {'s': 0, 'a': 1, 'b': 1, 'c': 2, 'd': 2, 'e': 2, 't': 3}
print(path_to(parent, "t"))                          # ['s', 'a', 'c', 't']

Key takeaways

BFS explores in layers of increasing distance, using a FIFO queue.
In an unweighted graph, it computes shortest-path distances and a shortest-path tree from s in O(n + m).
Mark vertices when they are enqueued. Recover paths by following parent pointers.
It is also the engine for connected components, bipartiteness testing and multi-source distances.

Practice

(Beginner) Run BFS on Q₃ from 000, visiting neighbors in increasing numeric order. List the layers and draw the BFS tree.

(Intermediate) Prove that in an undirected graph, |dist[u] − dist[v]| ≤ 1 for every edge {u, v} after BFS from s. Use it to explain why an edge between two vertices in the same layer means the graph is not bipartite.

(Interview) Word ladder. Given a start word, a target word and a dictionary, find the fewest single-letter changes that turn the start into the target, with every intermediate word in the dictionary. Hint: words are vertices and one-letter changes are edges, but do not build the graph explicitly. Generate the neighbors of each word on the fly (or group words by patterns such as h*t) and run BFS.

Depth-First Search

disc[v]: when v is first entered, and
fin[v]: when v is finished, after all its descendants.

Edge classification. Relative to the DFS forest:

Edge type	From `u` to `w` where …	In undirected graphs?
Tree edge	`w` was discovered through this edge	Yes
Back edge	`w` is an ancestor of `u` (still open)	Yes
Forward edge	`w` is a finished descendant of `u`	No
Cross edge	`w` is finished and in another branch	No

In an undirected graph, every non-tree edge is a back edge. Key facts:

A directed graph has a cycle if and only if DFS finds a back edge. With three colors, white (unvisited), gray (open) and black (finished), a back edge is an edge into a gray vertex.
In a DAG, listing the vertices by decreasing finishing time gives a topological order (2.5). For every arc u → w, w finishes before u.
DFS is the basis of the SCC (8.3) and bridge (8.3) algorithms.

	BFS	DFS
Data structure	Queue (FIFO)	Stack (LIFO) or recursion
Visit order	By distance from the source	Deep first, then backtrack
Shortest paths (unweighted)	Yes	No
Typical uses	Distances, bipartiteness, nearest target	Cycles, topological sort, SCCs, bridges, backtracking
Memory	Up to a whole layer	Up to the longest path explored
Time	`O(n + m)`	`O(n + m)`

WHITE, GRAY, BLACK = 0, 1, 2

def topological_order(adj):
    """Iterative DFS: raise on a back edge, otherwise return vertices by decreasing finishing time."""
    color = {v: WHITE for v in adj}
    finished = []
    for s in adj:
        if color[s] != WHITE:
            continue
        color[s] = GRAY
        stack = [(s, iter(adj[s]))]
        while stack:
            v, it = stack[-1]
            for w in it:
                if color[w] == GRAY:                         # w is open on the stack: back edge
                    raise ValueError(f"cycle through {v} -> {w}")
                if color[w] == WHITE:
                    color[w] = GRAY
                    stack.append((w, iter(adj[w])))
                    break
            else:                                            # all neighbors handled: v finishes
                color[v] = BLACK
                finished.append(v)
                stack.pop()
    return finished[::-1]

dressing = {"undershorts": ["pants", "shoes"], "pants": ["belt", "shoes"], "belt": ["jacket"],
            "shirt": ["belt", "tie"], "tie": ["jacket"], "jacket": [], "socks": ["shoes"], "shoes": []}
print(topological_order(dressing))
# ['socks', 'shirt', 'tie', 'undershorts', 'pants', 'shoes', 'belt', 'jacket']

try:
    topological_order({"a": ["b"], "b": ["c"], "c": ["a"]})
except ValueError as e:
    print(e)                                                 # cycle through c -> a

Key takeaways

DFS goes as deep as possible, then backtracks. It runs in O(n + m) with a stack or with recursion.
Discovery and finishing times are properly nested (parenthesis theorem).
A directed graph is acyclic exactly when DFS finds no back edge (no edge into a gray vertex).
Decreasing finishing time is a topological order of a DAG.
Prefer an explicit stack for deep graphs: recursion depth can reach n.

Practice

(Beginner) Run DFS on the BFS example graph above from s, visiting neighbors in alphabetical order. Give the discovery and finishing times and classify every edge.

(Intermediate) Prove that in a DFS of an undirected graph there are no cross edges, so every edge joins a vertex to one of its ancestors or descendants in the DFS tree.

(Interview) Course schedule. Given n courses and prerequisite pairs, decide whether all courses can be completed and, if so, return a valid order. Compare a DFS-based solution with Kahn's algorithm (2.5). Hint: both run in O(n + m). DFS detects the cycle through a gray vertex, while Kahn's algorithm detects it when some vertices never reach in-degree 0.

Euler Paths and Circuits

What. In a graph or multigraph:

An Euler circuit is a closed trail that uses every edge exactly once.
An Euler path (Euler trail) is a trail that uses every edge exactly once, not necessarily closed.

Theorem (Euler, Hierholzer). Let G be a connected multigraph (ignore isolated vertices).

G has an Euler circuit if and only if every vertex has even degree.
G has an Euler path but no Euler circuit if and only if exactly two vertices have odd degree. Every Euler path then starts at one of them and ends at the other.

Königsberg. Four land masses and seven bridges give a multigraph with degrees 5, 3, 3, 3. All four are odd, so there is no Euler path, let alone a circuit.

        north bank C
          ║        ╲
          ║ 2       ╲ 1
          ║          ╲
       island A ── 1 ── D east              degrees: A = 5, B = 3, C = 3, D = 3
          ║          ╱                      four odd vertices: no Euler path
          ║ 2       ╱ 1
          ║        ╱
        south bank B                        (║ = two parallel bridges)

          5
        ╱   ╲
       4 ─── 3            deg: 1 → 3, 2 → 3, 3 → 4, 4 → 4, 5 → 2
       │ ╲ ╱ │            odd vertices: 1 and 2
       │  ╳  │
       │ ╱ ╲ │
       1 ─── 2

from collections import defaultdict

def euler_path(edges):
    """Hierholzer's algorithm for an undirected multigraph. Returns a vertex sequence or None."""
    adj = defaultdict(list)
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    odd = [v for v in adj if len(adj[v]) % 2 == 1]
    if len(odd) not in (0, 2):
        return None
    start = odd[0] if odd else next(iter(adj))
    used, stack, trail = [False] * len(edges), [start], []
    while stack:
        v = stack[-1]
        while adj[v] and used[adj[v][-1][1]]:
            adj[v].pop()                                  # discard edges already used from the other end
        if adj[v]:
            w, i = adj[v].pop()
            used[i] = True
            stack.append(w)                               # keep walking along unused edges
        else:
            trail.append(stack.pop())                     # stuck: v is final, splice point for sub-tours
    return trail[::-1] if len(trail) == len(edges) + 1 else None   # None if disconnected

house = [(1, 2), (2, 3), (3, 4), (4, 1), (1, 3), (2, 4), (4, 5), (5, 3)]
print(euler_path(house))                                  # [1, 3, 5, 4, 2, 3, 4, 1, 2]

konigsberg = [("A", "B"), ("A", "B"), ("A", "C"), ("A", "C"), ("A", "D"), ("B", "D"), ("C", "D")]
print(euler_path(konigsberg))                             # None

Key takeaways

Euler circuit: every edge exactly once, ending where it started. It exists in a connected graph exactly when every degree is even.
Euler path: exactly zero or two odd-degree vertices, and with two, the path runs between them.
The proof is constructive: Hierholzer's algorithm splices closed trails and runs in O(m).
The directed version replaces "even degree" with "in-degree equals out-degree".

Practice

(Beginner) Which of these have an Euler circuit, and which only an Euler path: K₄, K₅, C₇, W₄, Q₃, Q₄, K_{2,4}, K_{3,3}?

(Intermediate) A road inspector must drive along every street of a town and return to the depot, and the street graph has 2k odd-degree vertices. Explain why at least k streets must be driven twice, and why k repeated streets may not be enough. Hint: repeating a street adds a parallel edge and changes the parity of two degrees. This is the Chinese postman problem.

(Interview) Reconstruct an itinerary. Given a list of airline tickets (from, to) that together form one trip starting at JFK, reconstruct the trip, using every ticket exactly once. Hint: tickets are arcs of a directed multigraph, and the trip is an Euler path. Run Hierholzer's algorithm and output vertices as they are finished, in reverse.

Hamiltonian Paths and Circuits

What.

A Hamiltonian path visits every vertex exactly once.
A Hamiltonian cycle (circuit) is a cycle that visits every vertex exactly once and returns to the start.
A graph with a Hamiltonian cycle is Hamiltonian.

The name comes from Hamilton's 1857 "Icosian game": find a cycle through all 20 vertices of a dodecahedron.

	Euler circuit	Hamiltonian cycle
Uses every … exactly once	Edge	Vertex
Simple characterization	Yes: connected and all degrees even	None known
Complexity of deciding	`O(n + m)`	NP-complete
Algorithm	Hierholzer, `O(m)`	Backtracking `O(n!)`, dynamic programming `O(2ⁿ n²)`

Sufficient conditions. These guarantee a Hamiltonian cycle in a simple graph with n ≥ 3 vertices. They are not necessary: Cₙ is Hamiltonian, yet all its degrees are 2.

Dirac (1952): deg(v) ≥ n/2 for every vertex v.
Ore (1960): deg(u) + deg(v) ≥ n for every pair of non-adjacent vertices u, v.

Obstructions. Each of these rules out a Hamiltonian cycle:

a vertex of degree 1, or a cut vertex (8.3);
a set of k vertices whose removal leaves more than k components (a Hamiltonian cycle minus k vertices falls into at most k pieces);
a bipartite graph with parts of different sizes (a Hamiltonian cycle alternates between the parts).

For example, K_{2,3} has no Hamiltonian cycle. The Petersen graph (three-regular, 10 vertices) has a Hamiltonian path but no Hamiltonian cycle.

def gray_code(n):
    if n == 0:
        return [""]
    prev = gray_code(n - 1)
    return ["0" + c for c in prev] + ["1" + c for c in reversed(prev)]   # reflect

codes = gray_code(3)
print(codes)                     # ['000', '001', '011', '010', '110', '111', '101', '100']
print(all(sum(a != b for a, b in zip(codes[i], codes[(i + 1) % 8])) == 1 for i in range(8)))   # True

def hamiltonian(n, edges, cycle=False):
    """Held–Karp style DP over vertex subsets, encoded as bitmasks."""
    nbr = [0] * n
    for u, v in edges:
        nbr[u] |= 1 << v
        nbr[v] |= 1 << u
    ends = [0] * (1 << n)                        # ends[S]: bitset of possible last vertices
    for v in ([0] if cycle else range(n)):       # a cycle can be assumed to start at vertex 0
        ends[1 << v] = 1 << v
    for S in range(1 << n):
        for v in range(n):
            if ends[S] >> v & 1:
                ext = nbr[v] & ~S                # neighbors of v not yet visited
                while ext:
                    w = ext & -ext               # lowest set bit
                    ends[S | w] |= w
                    ext ^= w
    full = ends[(1 << n) - 1]
    return bool(full & nbr[0]) if cycle else full != 0     # a cycle must close back to vertex 0

petersen = ([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
            + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])
print(hamiltonian(10, petersen), hamiltonian(10, petersen, cycle=True))   # True False

K23 = [(a, b) for a in (0, 1) for b in (2, 3, 4)]
print(hamiltonian(5, K23), hamiltonian(5, K23, cycle=True))               # True False

Key takeaways

A Hamiltonian path or cycle visits every vertex exactly once.
Unlike the Euler case, no simple characterization is known, and deciding is NP-complete.
Dirac's and Ore's conditions are sufficient. Cut vertices, leaves and unbalanced bipartite graphs are obstructions.
Qₙ is Hamiltonian (Gray codes). The Petersen graph is not.
The Held–Karp dynamic program decides it in O(2ⁿ n²), which is practical up to about n = 25.

Practice

(Beginner) Find a Hamiltonian cycle in K_{3,3}, in W₅, and in Q₃ (using the Gray code above). Explain why K_{3,4} has none.

(Intermediate) Prove by induction that the reflected Gray code of order n is a Hamiltonian cycle of Qₙ for n ≥ 2. Hint: the two halves are paths by the induction hypothesis. Check the two "seams" where the halves meet, including the wrap-around.

(Interview) A puzzle asks whether a knight can visit every square of a 5 × 5 board exactly once. How would you solve it, and how would your approach change for 8 × 8? Hint: this is a Hamiltonian path in the knight's-move graph. Bitmask DP needs 2²⁵ states, which is borderline, while backtracking with Warnsdorff's heuristic (always move to the square with the fewest onward moves) finds 8 × 8 tours almost instantly.

Dijkstra's Shortest Path Algorithm

How. Dijkstra's algorithm keeps a tentative distance dist[v] (initially ∞, and 0 for s) and a set of finalized vertices. It repeats:

Pick the non-finalized vertex u with the smallest dist[u], and finalize it.
Relax each edge (u, w): if dist[u] + w(u, w) < dist[w], lower dist[w] and set parent[w] = u.

Example.

     A ──4── B ──5── D ──6── F
      ╲     ╱         ╲     ╱
       2   1           2   3
        ╲ ╱             ╲ ╱
         C ──────10────── E

Step	Finalize	`B`	`C`	`D`	`E`	`F`
0		∞	∞	∞	∞	∞
1	`A`	4	2	∞	∞	∞
2	`C`	3	2	∞	12	∞
3	`B`	3	2	8	12	∞
4	`D`	3	2	8	10	14
5	`E`	3	2	8	10	13
6	`F`	3	2	8	10	13

Complexity.

Priority queue	Time	Best for
Unsorted array	`O(n²)`	Dense graphs
Binary heap	`O((n + m) log n)`	Sparse graphs, the usual choice
Fibonacci heap	`O(m + n log n)`	Theoretical bound

import heapq

def dijkstra(adj, s):
    dist, parent = {s: 0}, {s: None}
    heap, done = [(0, s)], set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in done:
            continue                                   # stale entry: u was finalized with a smaller key
        done.add(u)
        for w, weight in adj[u]:
            nd = d + weight
            if nd < dist.get(w, float("inf")):         # relax the edge u -> w
                dist[w], parent[w] = nd, u
                heapq.heappush(heap, (nd, w))          # lazy insert instead of decrease-key
    return dist, parent

def undirected(edges):
    adj = {}
    for u, v, w in edges:
        adj.setdefault(u, []).append((v, w))
        adj.setdefault(v, []).append((u, w))
    return adj

roads = undirected([("A", "B", 4), ("B", "D", 5), ("D", "F", 6), ("A", "C", 2),
                    ("C", "B", 1), ("D", "E", 2), ("E", "F", 3), ("C", "E", 10)])
dist, parent = dijkstra(roads, "A")
print(dict(sorted(dist.items())))                      # {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10, 'F': 13}
path, v = [], "F"
while v:
    path.append(v)
    v = parent[v]
print(path[::-1])                                      # ['A', 'C', 'B', 'D', 'E', 'F']

# A negative edge breaks the invariant: a is finalized at 2 before the cheaper route through b is seen.
neg = {"s": [("a", 2), ("b", 5)], "a": [("t", 1)], "b": [("a", -4)], "t": []}
print(dijkstra(neg, "s")[0]["t"])                      # 3, but the true distance s -> b -> a -> t is 2

Key takeaways

Dijkstra's algorithm finds shortest paths from one source when all weights are non-negative.
It finalizes vertices in order of distance and relaxes the edges out of each finalized vertex.
With a binary heap it runs in O((n + m) log n).
Negative weights break it. Use Bellman–Ford instead, or BFS when all weights are equal.

Practice

(Beginner) Run Dijkstra's algorithm on the example graph from F. Fill in the table and give the shortest path to A.

(Intermediate) Adding the same constant to every edge weight does not "fix" negative weights. Give a small graph where it changes which path is shortest. Hint: the constant is added once per edge, so it penalizes paths with many edges.

(Interview) A flight search must find the cheapest route from src to dst with at most k stops. Why does plain Dijkstra fail, and what would you do? Hint: the state must include the number of edges used, (vertex, stops). Either run Dijkstra on that expanded state space or run k + 1 rounds of Bellman–Ford relaxation.

Traveling Salesperson Problem

`n`	Distinct tours `(n − 1)!/2`
5	12
10	181,440
20	about `6.1 · 10¹⁶`
50	about `3 · 10⁶²`

How. Exact methods:

Brute force over all tours, O(n!): hopeless beyond about 12 cities.
Held–Karp dynamic programming, O(n² 2ⁿ): let C(S, v) be the cheapest path that starts at city 0, visits exactly the cities in S, and ends at v ∈ S. Then C(S, v) = min over u ∈ S − {v} of C(S − {v}, u) + w(u, v). It is practical up to about 25 cities.
Branch and bound and integer linear programming with cutting planes. The Concorde solver has solved instances with tens of thousands of cities to proven optimality.

Approximate methods:

Nearest neighbor: always go to the closest unvisited city. It is fast, but it can be far from optimal.
Local search, such as 2-opt: repeatedly reverse a segment of the tour if that removes two crossing edges and shortens it. It is very effective in practice.
Guaranteed approximations for metric TSP, where distances satisfy the triangle inequality w(u, v) ≤ w(u, x) + w(x, v). Walking around a minimum spanning tree (9.4) and skipping repeated cities gives a tour at most twice the optimum. Christofides' algorithm gets within a factor of 1.5. Without the triangle inequality, no constant-factor approximation exists unless P = NP.

from itertools import combinations

D = [[0, 2, 9, 10, 7],                      # symmetric distance matrix for 5 cities
     [2, 0, 6, 4, 3],
     [9, 6, 0, 8, 5],
     [10, 4, 8, 0, 6],
     [7, 3, 5, 6, 0]]
n = len(D)

def held_karp(D):
    """C[(S, v)]: cheapest path from city 0 through exactly the cities in bitmask S, ending at v."""
    n = len(D)
    C = {(1 << v, v): (D[0][v], 0) for v in range(1, n)}            # (cost, previous city)
    for size in range(2, n):
        for subset in combinations(range(1, n), size):
            S = sum(1 << v for v in subset)
            for v in subset:
                prev = S & ~(1 << v)
                C[(S, v)] = min((C[(prev, u)][0] + D[u][v], u) for u in subset if u != v)
    full = (1 << n) - 2                                              # every city except 0
    cost, last = min((C[(full, v)][0] + D[v][0], v) for v in range(1, n))
    tour, S = [], full
    while last:                                                      # follow the stored predecessors back
        tour.append(last)
        S, last = S & ~(1 << last), C[(S, last)][1]
    return cost, [0] + tour[::-1]

def nearest_neighbor(D, start=0):
    tour, left = [start], set(range(len(D))) - {start}
    while left:
        nxt = min(left, key=lambda j: D[tour[-1]][j])                # greedy: closest unvisited city
        tour.append(nxt)
        left.remove(nxt)
    return sum(D[tour[i]][tour[(i + 1) % len(tour)]] for i in range(len(tour))), tour

print(held_karp(D))                                                  # (26, [0, 4, 2, 3, 1])
print(nearest_neighbor(D))                                           # (28, [0, 1, 4, 2, 3])

Key takeaways

TSP asks for a minimum-weight Hamiltonian cycle in a complete weighted graph. It has (n − 1)!/2 tours.
It is NP-hard. Held–Karp solves it exactly in O(n² 2ⁿ), and practical solvers use branch and bound or integer programming.
Heuristics such as nearest neighbor and 2-opt give good tours quickly, without a guarantee.
With the triangle inequality, MST-based methods give guaranteed approximations (factor 2, or 1.5 for Christofides).

Practice

(Beginner) How many distinct tours are there on 6 cities with symmetric distances? Enumerate them for 4 cities A, B, C, D and find the cheapest when w(A,B) = 1, w(A,C) = 3, w(A,D) = 4, w(B,C) = 2, w(B,D) = 5, w(C,D) = 1.

(Intermediate) Prove that the weight of a minimum spanning tree is at most the weight of an optimal tour. Then explain why walking around the tree and skipping repeated cities gives a tour of at most twice the optimum when the triangle inequality holds. Hint: deleting one edge from a tour leaves a spanning tree.

(Interview) A courier app must reorder 150 stops in under one second each time a new order arrives. What would you implement, and how would you measure its quality without knowing the optimum? Hint: start with a fast construction (nearest neighbor or insertion), improve it with 2-opt for the time available, and reuse the previous tour when a stop is added. Compare against a lower bound such as the MST weight.

8.5 Planarity and Coloring

Planar Graphs

K₄ is planar, even though its most obvious drawing has a crossing:

   drawn with a crossing        drawn without crossings
                                          a
      a ──────── b                      ╱ │ ╲
      │ ╲      ╱ │                     ╱  │  ╲
      │   ╲  ╱   │                    ╱   d   ╲
      │    ╱╲    │                   ╱  ╱   ╲  ╲
      │  ╱    ╲  │                  ╱ ╱       ╲ ╲
      c ──────── d                 b ─────────── c

  Σ_{faces F} deg(F) = 2m

which is the handshaking lemma for faces.

Examples.

Planar	Not planar
All trees, all cycles `Cₙ`, all wheels `Wₙ`	`K₅`
`K₄`, `K_{2,n}` for every `n`	`K_{3,3}` (the "three utilities" puzzle)
`Q₃` (the cube) and the graphs of all convex polyhedra	`Kₙ` for `n ≥ 5`, `K_{m,n}` for `m, n ≥ 3`
Road networks without bridges and tunnels, maps	The Petersen graph

def orient(p, q, r):                                   # sign of the turn p -> q -> r
    return (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])

def crossings(pos, edges):
    """Count pairs of straight edges that cross (edges sharing an endpoint never count)."""
    count = 0
    for i, (a, b) in enumerate(edges):
        for c, d in edges[i + 1:]:
            if {a, b} & {c, d}:
                continue
            P, Q, R, S = pos[a], pos[b], pos[c], pos[d]
            if orient(P, Q, R) * orient(P, Q, S) < 0 and orient(R, S, P) * orient(R, S, Q) < 0:
                count += 1                             # each segment separates the other's endpoints
    return count

K4 = [("a", "b"), ("a", "c"), ("a", "d"), ("b", "c"), ("b", "d"), ("c", "d")]
square   = {"a": (0, 2), "b": (2, 2), "c": (0, 0), "d": (2, 0)}
triangle = {"a": (2, 4), "b": (0, 0), "c": (4, 0), "d": (2, 1)}
print(crossings(square, K4), crossings(triangle, K4))   # 1 0

Key takeaways

A graph is planar if some drawing of it has no crossing edges. One bad drawing proves nothing.
A plane drawing splits the plane into faces, and the face degrees add up to 2m.
K₄, trees, cycles, wheels and Q₃ are planar. K₅ and K_{3,3} are not.
Every planar graph has a straight-line planar drawing (Fáry), and planarity can be tested in linear time.

Practice

(Beginner) Draw Q₃ and W₅ without crossings, and count the faces of each drawing.

(Intermediate) Show that K_{2,n} is planar for every n, and that K₅ minus any one edge is planar, by giving explicit drawings.

(Interview) A diagram tool lays out a dependency graph and the output is full of crossings. The user asks whether a crossing-free layout exists. How would you answer, and what would you show the user when it does not exist? Hint: run a linear-time planarity test. When it fails, it can return a subdivision of K₅ or K_{3,3} as a certificate. Minimizing the number of crossings, as opposed to deciding whether it can be zero, is NP-hard.

Euler's Formula

What. For a connected plane graph with n vertices, m edges and f faces,

  n − m + f = 2

Proof by induction on m (3.2). A connected graph with n vertices has at least n − 1 edges (8.3).

Basis m = n − 1: the graph is a tree (9.1). A tree has no cycles, so it does not enclose any region, and f = 1. Then n − (n − 1) + 1 = 2.
Step m ≥ n: the graph is not a tree, so it has a cycle. Remove an edge e of the cycle. The graph stays connected, and the two faces on either side of e (different faces, because a cycle separates the plane into an inside and an outside) merge into one. So n is unchanged and m and f both drop by 1. By the induction hypothesis, n − (m − 1) + (f − 1) = 2, which equals n − m + f.

For a plane graph with c connected components, the formula becomes n − m + f = 1 + c. For a convex polyhedron, it is Euler's polyhedron formula V − E + F = 2:

Solid	`V`	`E`	`F`	`V − E + F`
Tetrahedron	4	6	4	2
Cube	8	12	6	2
Octahedron	6	12	8	2
Dodecahedron	20	30	12	2
Icosahedron	12	30	20	2

Corollaries. Let G be a simple planar graph with n ≥ 3 vertices.

m ≤ 3n − 6. For a connected G, every face has degree at least 3 (there are no loops or multiple edges, and a graph with n ≥ 3 is not a single edge). So 2m = Σ deg(F) ≥ 3f. Substituting f ≤ 2m/3 into Euler's formula gives 2 = n − m + f ≤ n − m/3. If G is disconnected, add edges until it is connected, which keeps it planar.
m ≤ 2n − 4 if G has no triangles (in particular, if G is bipartite). Now every face has degree at least 4, so 2m ≥ 4f. More generally, if the shortest cycle has length g, then m ≤ g(n − 2)/(g − 2).
G has a vertex of degree at most 5. Otherwise 2m = Σ deg(v) ≥ 6n, contradicting m ≤ 3n − 6.

Applications.

K₅: n = 5, m = 10 > 3 · 5 − 6 = 9. Not planar.
K_{3,3}: n = 6, m = 9 ≤ 12, so corollary 1 says nothing. But K_{3,3} is bipartite, and m = 9 > 2 · 6 − 4 = 8. Not planar.
The Petersen graph has n = 10, m = 15 and girth 5, so a planar drawing would need m ≤ 5 · 8/3 ≈ 13.3. Not planar.

These bounds are necessary conditions only. A graph can satisfy m ≤ 3n − 6 and still not be planar: K₅ plus 5 isolated vertices has n = 10 and m = 10 ≤ 24.

platonic = {"tetrahedron": (4, 6, 4), "cube": (8, 12, 6), "octahedron": (6, 12, 8),
            "dodecahedron": (20, 30, 12), "icosahedron": (12, 30, 20)}
print({name: V - E + F for name, (V, E, F) in platonic.items()})
# {'tetrahedron': 2, 'cube': 2, 'octahedron': 2, 'dodecahedron': 2, 'icosahedron': 2}

def edge_bound(n, girth=3):
    """Largest m allowed by Euler's formula for a simple planar graph with n >= 3 vertices."""
    return girth * (n - 2) / (girth - 2)

for name, n, m, g in [("K5", 5, 10, 3), ("K3,3", 6, 9, 4), ("Petersen", 10, 15, 5), ("Q3", 8, 12, 4)]:
    verdict = "not planar" if m > edge_bound(n, g) else "no conclusion"
    print(f"{name:9} m = {m:2}  bound = {edge_bound(n, g):5.2f}  {verdict}")
# K5        m = 10  bound =  9.00  not planar
# K3,3      m =  9  bound =  8.00  not planar
# Petersen  m = 15  bound = 13.33  not planar
# Q3        m = 12  bound = 12.00  no conclusion

Q₃ meets the bound with equality, and it is in fact planar: its planar drawing is the cube, all of whose faces are 4-cycles.

Key takeaways

For a connected plane graph, n − m + f = 2. Every planar drawing of the graph has the same number of faces.
Simple planar graphs are sparse: m ≤ 3n − 6, and m ≤ 2n − 4 without triangles.
K₅ and K_{3,3} violate these bounds, so they are not planar.
Every simple planar graph has a vertex of degree at most 5.
The bounds can prove non-planarity, but never planarity.

Practice

(Beginner) A connected planar graph has 10 vertices, each of degree 3. How many faces does every planar drawing of it have?

(Intermediate) Prove that a connected simple planar graph in which every face is a triangle has exactly 3n − 6 edges. Then show that the average degree of any simple planar graph is less than 6.

(Interview) Prove, using only Euler's formula, that there are exactly five Platonic solids (convex polyhedra in which every face is a regular p-gon and every vertex has degree q). Hint: pF = 2E = qV. Substitute into V − E + F = 2 to get 1/p + 1/q = 1/2 + 1/E > 1/2, and list the integer solutions with p, q ≥ 3.

Kuratowski's Theorem

Kuratowski's theorem. A graph is planar if and only if it contains no subgraph that is a subdivision of K₅ or of K_{3,3}.

One direction is easy: a subdivision of a non-planar graph is non-planar, and a subgraph of a planar graph is planar. The other direction is the deep part.

   K₃,₃                                 a subdivision of K₃,₃

   h₁      h₂      h₃                   h₁      h₂      h₃
   │ ╲   ╱ │ ╲   ╱ │                    │ ╲   ╱ │ ╲   ╱ │
   │   ╳   │   ╳   │                    s   ╳   │   ╳   t
   │ ╱   ╲ │ ╱   ╲ │                    │ ╱   ╲ │ ╱   ╲ │
   u₁      u₂      u₃                   u₁      u₂      u₃

   plus the two long edges h₁u₃ and h₃u₁ (not drawn) in both graphs.
   On the right, the edges h₁u₁ and h₃u₃ are replaced by the paths h₁, s, u₁ and h₃, t, u₃.

def smooth(adj):
    """Undo subdivisions: replace each degree-2 vertex u - v - w by a direct edge u - w."""
    adj = {v: set(ns) for v, ns in adj.items()}
    changed = True
    while changed:
        changed = False
        for v in list(adj):
            if len(adj[v]) == 2:
                a, b = adj[v]
                if b not in adj[a]:                       # do not create a parallel edge
                    adj[a] -= {v}; adj[b] -= {v}
                    adj[a].add(b); adj[b].add(a)
                    del adj[v]
                    changed = True
    return adj

def is_K33(adj):
    if len(adj) != 6 or any(len(ns) != 3 for ns in adj.values()):
        return False
    v = next(iter(adj))
    side = adj[v]                                         # in K3,3, v's neighbors form the other side
    other = set(adj) - side
    return all(adj[x] == other for x in side) and all(adj[y] == side for y in other)

edges = ([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
         + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])  # Petersen: outer 5-cycle, spokes, inner pentagram
petersen = {v: set() for v in range(10)}
for u, v in edges:
    petersen[u].add(v); petersen[v].add(u)

minus0 = {v: ns - {0} for v, ns in petersen.items() if v != 0}       # delete vertex 0
print(sorted(v for v, ns in minus0.items() if len(ns) == 2))      # [1, 4, 5]   the subdivision vertices
core = smooth(minus0)
print(sorted(core), is_K33(core))                                 # [2, 3, 6, 7, 8, 9] True

Key takeaways

A subdivision replaces edges by paths. It does not change planarity.
Kuratowski: a graph is planar exactly when it contains no subdivision of K₅ or K_{3,3}.
Wagner: equivalently, a graph is planar exactly when it has no K₅ or K_{3,3} minor.
A Kuratowski subgraph is a certificate of non-planarity, and linear-time planarity tests can produce one.

Practice

(Beginner) Show that K_{3,3} minus one edge is planar by drawing it. Then explain why the graph obtained from K₅ by subdividing every edge once is still not planar, even though it is bipartite.

(Intermediate) Show that Q₄ is not planar, first with Euler's formula, then by finding a subdivision of K_{3,3} in it. Hint: Q₄ is bipartite with n = 16 and m = 32.

(Interview) Explain why the brute-force strategy "try every subset of edges and test whether it is a subdivision of K₅ or K_{3,3}" is impractical, and how the linear-time planarity algorithms avoid it. Hint: there are 2ᵐ subsets. Efficient algorithms build an embedding incrementally (for example, adding vertices in DFS order) and extract a Kuratowski subgraph only at the point where the embedding gets stuck.

Graph Coloring

How: greedy coloring. Take the vertices in some order and give each one the smallest color not used by its already-colored neighbors.

A vertex has at most Δ neighbors, so some color among 1, …, Δ + 1 is always free. Greedy coloring therefore uses at most Δ + 1 colors, and it runs in O(n + m) time.
The result depends heavily on the order. For every graph, some order makes greedy coloring optimal, but finding it is as hard as the coloring problem itself. Welsh–Powell (largest degree first) and DSatur (most distinct neighbor colors first) are good heuristics.

Example: exam scheduling. Four students take these courses: {Math, Physics, CS}, {CS, Chem}, {Chem, Bio} and {Bio, Art, Math}. Two courses conflict when a student takes both.

        Physics
        ╱     ╲
     Math ───── CS              Math, Physics, CS form a triangle,
      │  ╲        ╲             so at least 3 time slots are needed
      │   ╲        Chem
      │    ╲      ╱
     Art ── Bio ─╯

def greedy_coloring(adj, order):
    color = {}
    for v in order:
        used = {color[w] for w in adj[v] if w in color}
        color[v] = next(c for c in range(len(adj)) if c not in used)   # smallest free color
    return color

students = [{"Math", "Physics", "CS"}, {"CS", "Chem"}, {"Chem", "Bio"}, {"Bio", "Art", "Math"}]
conflicts = {c: set() for s in students for c in s}
for s in students:
    for c in s:
        conflicts[c] |= s - {c}                                        # courses sharing a student

welsh_powell = sorted(conflicts, key=lambda c: (-len(conflicts[c]), c))   # largest degree first
slots = greedy_coloring(conflicts, welsh_powell)
print(welsh_powell)                    # ['Math', 'Bio', 'CS', 'Art', 'Chem', 'Physics']
print(slots)                           # {'Math': 0, 'Bio': 1, 'CS': 1, 'Art': 2, 'Chem': 0, 'Physics': 2}

n = 4                                  # crown graph on a1..a4, b1..b4
crown = {f"{s}{i}": {f"{t}{j}" for j in range(1, n + 1) if j != i}
         for s, t in [("a", "b"), ("b", "a")] for i in range(1, n + 1)}
interleaved = [f"{s}{i}" for i in range(1, n + 1) for s in "ab"]
by_side = sorted(crown)                                            # a1..a4, then b1..b4
print(len(set(greedy_coloring(crown, interleaved).values())))      # 4
print(len(set(greedy_coloring(crown, by_side).values())))          # 2

Key takeaways

A proper coloring gives adjacent vertices different colors, and each color class is an independent set.
Scheduling, frequency assignment and register allocation are coloring problems on a conflict graph.
Greedy coloring uses at most Δ + 1 colors, but the result depends on the vertex order.
Welsh–Powell and DSatur choose good orders, but no fast method is optimal on every graph.

Practice

(Beginner) Color C₆, C₇, W₆ and Q₃ with as few colors as you can, and argue that you cannot use fewer.

(Intermediate) Prove that greedy coloring never uses more than Δ + 1 colors. Then prove that for every graph there is an order in which greedy coloring uses exactly χ(G) colors (next topic). Hint: take an optimal coloring and list its color classes one after another.

(Interview) In a compiler, two variables interfere if they are live at the same time, and each must get one of k registers. How do you model this, and what do you do when the graph needs more than k colors? Hint: this is coloring of the interference graph. Chaitin-style allocators repeatedly remove vertices of degree less than k (they can always be colored later), and "spill" a variable to memory when no such vertex remains.

Chromatic Number

What. The chromatic number χ(G) is the smallest k for which G is k-colorable.

Graph	`χ`	Reason
No edges	1
Bipartite with at least one edge, including trees, even cycles and `Qₙ`	2	2-colorable (8.1)
`Cₙ`, `n` odd	3	Odd cycles are not bipartite
`Kₙ`	`n`	All vertices are pairwise adjacent
`Wₙ`, `n` even	3	The rim takes 2 colors, the hub a third
`Wₙ`, `n` odd	4	The odd rim takes 3 colors, the hub a fourth
Petersen graph	3	Contains a 5-cycle, and a 3-coloring exists
Planar graphs	`≤ 4`	Four Color Theorem (next topic)

Bounds. Let ω(G) be the size of the largest clique and α(G) the size of the largest independent set.

χ(G) ≥ ω(G): a clique needs all different colors.
χ(G) ≥ n / α(G): each color class is an independent set, so it has at most α vertices.
χ(G) ≤ Δ(G) + 1: greedy coloring.
Brooks' theorem: χ(G) ≤ Δ(G) for a connected graph, unless G is a complete graph or an odd cycle.

P(Kₙ, k) = k(k − 1)(k − 2) ⋯ (k − n + 1), a falling factorial (5.2).
P(T, k) = k(k − 1)ⁿ⁻¹ for every tree T on n vertices: color the root, then each child avoids its parent's color.
P(Cₙ, k) = (k − 1)ⁿ + (−1)ⁿ(k − 1).
Deletion–contraction: P(G, k) = P(G − e, k) − P(G / e, k). Colorings of G − e either give the endpoints of e different colors (colorings of G) or the same color (colorings of G / e, where the two endpoints are merged).

from itertools import product

def colorable(adj, k):
    """Backtracking: try to color the vertices in order with k colors."""
    order, color = list(adj), {}
    def place(i):
        if i == len(order):
            return True
        v = order[i]
        for c in range(k):
            if all(color.get(w) != c for w in adj[v]):
                color[v] = c
                if place(i + 1):
                    return True
                del color[v]                               # backtrack
        return False
    return place(0)

def chromatic_number(adj):
    return next(k for k in range(1, len(adj) + 1) if colorable(adj, k))

def build(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

wheel = lambda n: build([(i, (i + 1) % n) for i in range(n)] + [(i, "hub") for i in range(n)])
petersen = build([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
                 + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])
print(chromatic_number(wheel(6)), chromatic_number(wheel(5)), chromatic_number(petersen))   # 3 4 3

# Count proper 3-colorings of C5 by brute force and compare with (k-1)^n + (-1)^n (k-1)
C5 = [(i, (i + 1) % 5) for i in range(5)]
count = sum(all(c[u] != c[v] for u, v in C5) for c in product(range(3), repeat=5))
print(count, (3 - 1) ** 5 + (-1) ** 5 * (3 - 1))           # 30 30

Key takeaways

χ(G) is the fewest colors in a proper coloring.
ω(G) ≤ χ(G) ≤ Δ(G) + 1, and Brooks improves the upper bound to Δ except for complete graphs and odd cycles.
χ ≤ 2 exactly for bipartite graphs, and deciding χ ≤ 3 is NP-complete.
The chromatic polynomial counts colorings, and deletion–contraction computes it.

Practice

(Beginner) Find χ for K_{3,4}, C₉, W₈, W₉, and the graph formed by two triangles sharing an edge.

(Intermediate) Prove that χ(G) · α(G) ≥ n, and use it to show that χ(C₇ complement) ≥ 4. Then verify P(C₄, k) = (k − 1)⁴ + (k − 1) using deletion–contraction on one edge.

(Interview) Model a Sudoku puzzle as a graph coloring problem. How many vertices and edges does the graph have, what is its chromatic number, and how does a solver use the given digits? Hint: 81 cells, each adjacent to the other cells in its row, column and box (20 neighbors each, so 81 · 20 / 2 = 810 edges). The given digits are a precoloring, and the solver extends it by backtracking with constraint propagation.

Four Color Theorem

Four Color Theorem (Appel and Haken, 1976). Every planar graph is 4-colorable. Equivalently, every map can be colored with 4 colors so that neighboring regions get different colors.

Four colors are sometimes necessary. K₄ is planar, and the map below has four regions that all touch each other:

   ┌─────────────────────────┐
   │            A            │       A borders B, C and D
   │    ┌───────────────┐    │       B borders C and D
   │    │       B       │    │       C borders D
   │    ├───────┬───────┤    │
   │    │   C   │   D   │    │       dual graph = K₄, so 4 colors are needed
   └────┴───────┴───────┴────┘

History.

Year	Event
1852	Guthrie poses the problem
1879	Kempe publishes a "proof"
1890	Heawood finds the error in Kempe's argument and uses Kempe's ideas to prove that five colors always suffice
1976	Appel and Haken prove four colors suffice, checking 1,936 configurations by computer
1997	Robertson, Sanders, Seymour and Thomas give a simpler proof with 633 configurations, still computer-assisted
2005	Gonthier verifies the proof completely in the Coq proof assistant

def smallest_last_coloring(adj):
    """Greedy coloring in reverse smallest-last order. At most 6 colors on any planar graph."""
    remaining = {v: set(ns) for v, ns in adj.items()}
    removal = []
    while remaining:
        v = min(remaining, key=lambda x: len(remaining[x]))   # degree <= 5 in any planar graph
        removal.append(v)
        for w in remaining.pop(v):
            remaining[w].discard(v)
    color = {}
    for v in reversed(removal):                                # each v sees <= 5 colored neighbors
        used = {color[w] for w in adj[v] if w in color}
        color[v] = next(c for c in range(len(adj)) if c not in used)
    return color

# Icosahedron: top 0, upper ring 1..5, lower ring 6..10, bottom 11. 5-regular and planar.
ico = {v: set() for v in range(12)}
def link(u, v):
    ico[u].add(v); ico[v].add(u)
for i in range(5):
    link(0, 1 + i); link(11, 6 + i)
    link(1 + i, 1 + (i + 1) % 5); link(6 + i, 6 + (i + 1) % 5)              # the two rings
    link(1 + i, 6 + i); link(1 + i, 6 + (i + 1) % 5)                       # zigzag between the rings
print(sum(map(len, ico.values())) // 2, 3 * 12 - 6)                       # 30 30   a maximal planar graph
coloring = smallest_last_coloring(ico)
print(len(set(coloring.values())))                                         # 4
print(all(coloring[u] != coloring[v] for u in ico for v in ico[u]))        # True

Key takeaways

Every planar graph, and so every map, can be colored with 4 colors. Four is sometimes needed (K₄).
Six colors are easy (a vertex of degree at most 5 always exists), and five colors follow from Kempe chains.
The four-color proof checks hundreds of configurations by computer, and has been formally verified.
The theorem applies only to planar graphs. Conflict graphs in practice are usually not planar.

Practice

(Beginner) Draw the dual graph of a map of your choice with at least six regions (for example, a few neighboring countries), and 4-color it.

(Intermediate) Write out the six color theorem proof in full, using strong induction (3.2) and the corollary of Euler's formula. Where exactly is planarity used, and why does removing a vertex keep the graph planar?

(Interview) A colleague says, "Our exam-conflict graph only needs 4 time slots, by the Four Color Theorem." What is wrong with this argument, and what would you check? Hint: the theorem needs a planar graph, and a conflict graph containing K₅ (five courses taken together by one student) needs 5 slots. Check for large cliques, or test planarity.

Edge Coloring

Edge coloring is vertex coloring of the line graph L(G), whose vertices are the edges of G and whose edges join edges of G that share an endpoint.

Bounds. The edges at a vertex of maximum degree need Δ different colors, so χ'(G) ≥ Δ. For edges, the upper bound is surprisingly tight:

Vizing's theorem (1964): every simple graph has Δ ≤ χ'(G) ≤ Δ + 1. Graphs with χ' = Δ are class 1, and graphs with χ' = Δ + 1 are class 2. Deciding which class a graph belongs to is NP-complete.
König's theorem (1916): every bipartite graph has χ'(G) = Δ.

Graph	`Δ`	`χ'`
`Cₙ`, `n` even	2	2
`Cₙ`, `n` odd	2	3
`Kₙ`, `n` even	`n − 1`	`n − 1`
`Kₙ`, `n` odd	`n − 1`	`n`
`K_{m,n}`	`max(m, n)`	`max(m, n)` (König)
Petersen graph	3	4

def round_robin(n):
    """Circle method for an even number n of teams: a proper (n-1)-edge-coloring of K_n."""
    rounds = []
    for r in range(n - 1):
        matches = [(r, n - 1)]                                   # the fixed team plays team r
        for i in range(1, n // 2):
            matches.append(((r + i) % (n - 1), (r - i) % (n - 1)))   # pairs symmetric around r
        rounds.append(matches)
    return rounds

schedule = round_robin(6)
for r, matches in enumerate(schedule, 1):
    print(r, matches)
# 1 [(0, 5), (1, 4), (2, 3)]
# 2 [(1, 5), (2, 0), (3, 4)]
# 3 [(2, 5), (3, 1), (4, 0)]
# 4 [(3, 5), (4, 2), (0, 1)]
# 5 [(4, 5), (0, 3), (1, 2)]

all_matches = [frozenset(m) for rnd in schedule for m in rnd]
print(len(all_matches), len(set(all_matches)))                   # 15 15   every pair exactly once
print(all(len({t for m in rnd for t in m}) == 6 for rnd in schedule))   # True   each team once per round

Key takeaways

Edge coloring gives edges at a common vertex different colors, and each color class is a matching.
Vizing: χ'(G) is Δ or Δ + 1. König: bipartite graphs always need exactly Δ.
χ'(Kₙ) = n − 1 for even n and n for odd n, which is the number of rounds in a round-robin tournament.
Edge coloring of G is vertex coloring of the line graph L(G).

Practice

(Beginner) Find χ' for K₄, C₅, K_{2,3} and W₄, and give an optimal edge coloring for each.

(Intermediate) Prove that χ'(Kₙ) ≥ n when n is odd. Hint: a matching in Kₙ has at most (n − 1)/2 edges, and Kₙ has n(n − 1)/2 edges.

(Interview) Each of 10 engineers must have a one-on-one meeting with each of 4 managers, every meeting takes one hour, and a person can attend only one meeting per hour. What is the minimum number of hours, and how would you build the schedule? Hint: the meetings form the bipartite graph K_{4,10} with Δ = 10. König's theorem says 10 hours suffice. Build it by repeatedly removing a matching that covers every vertex of maximum degree, or by a direct rotation.

8.6 Matchings and Flows

Matchings

What. A matching M in a graph is a set of edges no two of which share an endpoint. A vertex touched by an edge of M is matched (saturated), and the others are free.

Term	Meaning
Maximal matching	No edge can be added to it
Maximum matching	Has the largest possible number of edges, `ν(G)`
Perfect matching	Every vertex is matched, so `

   matching M (═) and an augmenting path from x to y

   x ─── a ═══ b ─── c ═══ d ─── y          |M ∩ path| = 2
   free                          free

   after flipping the path (M Δ path)

   x ═══ a ─── b ═══ c ─── d ═══ y          |M ∩ path| = 3

Berge's theorem (1957). A matching is maximum if and only if there is no augmenting path for it.

How. Berge's theorem gives an algorithm: start with any matching and repeatedly find and flip an augmenting path.

Bipartite graphs, Kuhn's algorithm: for each vertex on the left, search for an augmenting path with DFS. O(nm).
Bipartite graphs, Hopcroft–Karp: find many shortest augmenting paths per phase. O(m √n).
General graphs, Edmonds' blossom algorithm (1965): odd cycles ("blossoms") complicate the search, and Edmonds handles them by shrinking them. Polynomial time.
Weighted bipartite matching (the assignment problem): the Hungarian algorithm, O(n³).

def max_bipartite_matching(adj):
    """Kuhn's algorithm. adj: left vertex -> list of right vertices. Returns (size, right -> left)."""
    match = {}

    def try_assign(u, seen):                     # DFS for an augmenting path starting at u
        for v in adj[u]:
            if v in seen:
                continue
            seen.add(v)
            if v not in match or try_assign(match[v], seen):   # v is free, or its partner can move
                match[v] = u                     # flip the path: u takes v
                return True
        return False

    size = sum(try_assign(u, set()) for u in adj)
    return size, match

skills = {"Ana": ["Backend", "Data"], "Ben": ["Backend"],
          "Cleo": ["Data", "Ops"], "Dev": ["Ops", "Frontend"]}
size, match = max_bipartite_matching(skills)
print(size, {worker: job for job, worker in sorted(match.items(), key=lambda p: p[1])})
# 4 {'Ana': 'Data', 'Ben': 'Backend', 'Cleo': 'Ops', 'Dev': 'Frontend'}

When Ben arrives, his only job, Backend, is already taken by Ana. The augmenting path Ben – Backend ═ Ana – Data moves Ana to Data and frees Backend for Ben.

Key takeaways

A matching is a set of disjoint edges. Maximal means nothing can be added. Maximum means the largest size. Perfect means every vertex is matched.
Berge: a matching is maximum exactly when no augmenting path exists. Flipping an augmenting path adds one edge.
Bipartite matching takes O(nm) with Kuhn's algorithm and O(m √n) with Hopcroft–Karp. General graphs need Edmonds' blossom algorithm.
König: in bipartite graphs, maximum matching size equals minimum vertex cover size.

Practice

(Beginner) Find a maximal matching that is not maximum in P₆ and in C₆. What is ν for Kₙ, Cₙ, K_{m,n} and the Petersen graph?

(Intermediate) Prove that every maximal matching has at least half as many edges as a maximum matching. Hint: every edge of a maximum matching shares an endpoint with some edge of the maximal matching, and each maximal-matching edge has only two endpoints.

(Interview) A ride-hailing service must pair waiting riders with nearby drivers every few seconds, where each driver can take one rider. How would you maximize the number of pairs, and what changes if you also want to minimize the total pickup distance? Hint: the first is maximum bipartite matching (Hopcroft–Karp). The second is the assignment problem (Hungarian algorithm or min-cost flow). In practice, batching windows trade waiting time for better matches.

Hall's Marriage Theorem

Hall's theorem (1935). G has a matching that saturates X if and only if

  |N(S)| ≥ |S|        for every subset S ⊆ X        (Hall's condition)

Necessity is obvious: the vertices of S must be matched to |S| different vertices, all in N(S).

Sufficiency (proof sketch by strong induction on |X|). Two cases.

If every non-empty proper subset S has |N(S)| ≥ |S| + 1 (some slack), match any vertex x ∈ X to any neighbor y. Removing x and y costs every remaining set at most one neighbor, so Hall's condition still holds, and the induction hypothesis matches the rest.
If some non-empty proper subset S is tight, |N(S)| = |S|, then match S into N(S) by induction. In the rest of the graph (X − S and Y − N(S)), Hall's condition still holds: if a set T ⊆ X − S had fewer than |T| new neighbors, S ∪ T would violate the condition in G. Match the rest by induction too.

Hall's theorem also follows from König's theorem or from max-flow min-cut (next topics).

Example.

   applicant   acceptable positions
       A       1, 2                     N({A, B, C}) = {1, 2}
       B       1                        three applicants compete for two positions,
       C       1, 2                     so Hall's condition fails for S = {A, B, C}
       D       2, 3, 4

Whatever happens, one of A, B, C is left without a position. The deficiency version of Hall's theorem says that the maximum matching has size |X| − max_S (|S| − |N(S)|) = 4 − 1 = 3.

Corollaries.

Every k-regular bipartite graph with k ≥ 1 has a perfect matching. For any S ⊆ X, the k|S| edges leaving S all land in N(S), which receives at most k|N(S)| edges, so |N(S)| ≥ |S|. Removing a perfect matching leaves a (k − 1)-regular bipartite graph, so repeating this gives König's edge coloring theorem (8.5) for regular bipartite graphs.
Systems of distinct representatives: sets A₁, …, Aₙ have distinct representatives aᵢ ∈ Aᵢ exactly when every union of k of them has at least k elements.

from itertools import combinations

def hall_violation(adj):
    """Return a subset S of the left side with the largest deficiency |S| - |N(S)|, or None."""
    worst, worst_def = None, 0
    left = sorted(adj)
    for k in range(1, len(left) + 1):
        for S in combinations(left, k):                  # 2^|X| subsets: fine for small X
            N = set().union(*(adj[x] for x in S))
            if len(S) - len(N) > worst_def:
                worst, worst_def = (S, sorted(N)), len(S) - len(N)
    return worst, worst_def

accepts = {"A": {1, 2}, "B": {1}, "C": {1, 2}, "D": {2, 3, 4}}
print(hall_violation(accepts))                           # ((('A', 'B', 'C'), [1, 2]), 1)
print(len(accepts) - hall_violation(accepts)[1])         # 3   = size of a maximum matching

accepts["C"].add(3)                                      # C now also accepts position 3
print(hall_violation(accepts))                           # (None, 0)   Hall's condition holds

Key takeaways

A matching saturating X exists exactly when every S ⊆ X has at least |S| neighbors.
A violating set S is a short certificate that no complete assignment exists.
The maximum matching size is |X| minus the largest deficiency |S| − |N(S)|.
Every k-regular bipartite graph has a perfect matching.

Practice

(Beginner) Check Hall's condition for X = {a, b, c} with N(a) = {1, 2}, N(b) = {2, 3}, N(c) = {1, 3}, and find a matching saturating X. Then change N(c) to {2} and find a violating set.

(Intermediate) Prove that every k-regular bipartite graph (k ≥ 1) has a perfect matching, and conclude that its edges can be colored with k colors.

(Interview) Remove two diagonally opposite corner squares from an 8 × 8 chessboard. Can the remaining 62 squares be covered by 31 dominoes? Explain the answer in the language of Hall's theorem. Hint: squares are vertices and dominoes are edges of a bipartite graph between black and white squares. Count the squares of each color: the larger color class cannot be matched into the smaller.

Network Flows

What. A flow network is a directed graph with a source s, a sink t, and a capacity c(u, v) ≥ 0 on each arc. A flow assigns a number f(u, v) to each arc so that

Capacity constraint: 0 ≤ f(u, v) ≤ c(u, v).
Conservation: at every vertex other than s and t, the flow in equals the flow out.

The value |f| of a flow is the net flow out of s, which by conservation equals the net flow into t. The maximum flow problem asks for a flow of largest value.

Analogy. Water pipes of different widths. Water enters at the source and leaves at the sink, no junction leaks or stores water, and no pipe carries more than its width allows.

Residual graph. Given a flow f, the residual graph describes how the flow can still change:

a forward residual arc u → v with capacity c(u, v) − f(u, v) (room to push more), and
a backward residual arc v → u with capacity f(u, v) (flow that can be cancelled, which redirects it).

How.

Ford–Fulkerson method (1956): start with the zero flow and repeatedly augment along any augmenting path until none exists. With integer capacities, each augmentation adds at least 1, so it terminates.
Edmonds–Karp algorithm: always choose a shortest augmenting path (BFS, 8.4). This guarantees O(nm²) time for any capacities.
Faster algorithms exist: Dinic's algorithm, O(n²m), push–relabel, and recent almost-linear-time algorithms (2022).

Reductions.

Problem	Flow model
Bipartite matching	`s → x` for each `x ∈ X`, `x → y` for each edge, `y → t` for each `y ∈ Y`, all capacity 1. Max flow = maximum matching
Several sources or sinks	Add a super-source joined to every source, and a super-sink, with infinite capacities
Vertex capacities	Split `v` into `v_in → v_out` with the vertex's capacity on that arc
Edge-disjoint `s`–`t` paths	Capacity 1 on every arc. Max flow = number of disjoint paths (Menger, 8.3)

Example.

                10              4               10
          s ──────────► a ──────────► b ──────────► t
           ╲            │ ╲           ▲             ▲
            ╲ 10      2 │  ╲ 8        │ 6           │
             ╲          ▼   ╲         │             │ 10
              ╰───────► c    ╰──────► d ────────────╯
                        │             ▲
                        ╰───── 9 ─────╯

The arcs are s→a (10), s→c (10), a→b (4), a→c (2), a→d (8), c→d (9), d→b (6), b→t (10) and d→t (10).

from collections import deque, defaultdict

def max_flow(arcs, s, t):
    """Edmonds–Karp. arcs: list of (u, v, capacity). Returns (value, residual capacities, reachable set)."""
    res = defaultdict(lambda: defaultdict(int))
    for u, v, c in arcs:
        res[u][v] += c                           # forward residual capacity
        res[v][u] += 0                           # create the backward residual arc
    value = 0
    while True:
        parent = {s: None}
        queue = deque([s])
        while queue and t not in parent:         # BFS: shortest augmenting path
            u = queue.popleft()
            for v, r in res[u].items():
                if r > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)
        if t not in parent:
            return value, res, set(parent)       # no augmenting path: the flow is maximum
        bottleneck, v = float("inf"), t
        while parent[v] is not None:
            bottleneck = min(bottleneck, res[parent[v]][v])
            v = parent[v]
        v = t
        while parent[v] is not None:             # push the bottleneck along the path
            u = parent[v]
            res[u][v] -= bottleneck
            res[v][u] += bottleneck              # allow it to be cancelled later
            v = u
        value += bottleneck

arcs = [("s", "a", 10), ("s", "c", 10), ("a", "b", 4), ("a", "c", 2), ("a", "d", 8),
        ("c", "d", 9), ("d", "b", 6), ("b", "t", 10), ("d", "t", 10)]
value, res, reachable = max_flow(arcs, "s", "t")
print(value)                                                     # 19
print({f"{u}{v}": c - res[u][v] for u, v, c in arcs})            # flow on each arc
# {'sa': 10, 'sc': 9, 'ab': 4, 'ac': 0, 'ad': 6, 'cd': 9, 'db': 5, 'bt': 9, 'dt': 10}
print(sorted(reachable))                                         # ['c', 's']   source side of a minimum cut

Check conservation at d: in 6 + 9 = 15, out 5 + 10 = 15. The vertex c can forward at most 9 units, through c → d, so s → c can never be used to its full capacity of 10.

Key takeaways

A flow respects arc capacities and is conserved at every vertex except s and t.
The residual graph has forward arcs (spare capacity) and backward arcs (flow that can be cancelled).
Ford–Fulkerson augments along residual paths until none remain. Edmonds–Karp uses BFS and runs in O(nm²).
With integer capacities, some maximum flow is integral, so matchings and disjoint paths reduce to flows.

Practice

(Beginner) In the example network, check that the flow printed above satisfies the capacity constraints and conservation at a, b, c and d.

(Intermediate) Show how to reduce maximum bipartite matching to maximum flow, and prove that an integral maximum flow gives a maximum matching. Then show how to handle a vertex that can carry at most k units of flow.

(Interview) A company must decide which of several projects to run. Each project has a profit, each requires some pieces of equipment, and each piece of equipment has a cost (paid once, shared by all projects that use it). How can this be solved with a minimum cut? Hint: this is the project selection problem. Join s to each project with its profit, each piece of equipment to t with its cost, and each project to its equipment with infinite capacity. The best net profit is the total profit minus the minimum cut.

Max-Flow Min-Cut Theorem

What. An s–t cut is a partition of the vertices into S and T = V − S with s ∈ S and t ∈ T. Its capacity is the total capacity of the arcs going from S to T:

  c(S, T) = Σ_{u ∈ S, v ∈ T} c(u, v)

Arcs from T back to S do not count.

Weak duality. For every flow f and every cut (S, T), |f| ≤ c(S, T).

So every cut capacity is an upper bound on every flow value. The theorem says the best of these bounds is exact.

f is a maximum flow.
The residual graph has no augmenting path.
|f| = c(S, T) for some cut (S, T).

The proof gives an algorithm: after Ford–Fulkerson stops, one last search from s in the residual graph finds a minimum cut, in O(m) time.

`S`	Arcs from `S` to `T`	Capacity
`{s}`	`s→a`, `s→c`	20
`{s, c}`	`s→a`, `c→d`	19
`{s, a}`	`s→c`, `a→b`, `a→c`, `a→d`	24
`{s, a, c}`	`a→b`, `a→d`, `c→d`	21
`{s, a, c, d}`	`a→b`, `d→b`, `d→t`	20
`{s, a, b, c, d}`	`b→t`, `d→t`	20

from itertools import combinations

arcs = [("s", "a", 10), ("s", "c", 10), ("a", "b", 4), ("a", "c", 2), ("a", "d", 8),
        ("c", "d", 9), ("d", "b", 6), ("b", "t", 10), ("d", "t", 10)]
inner = ["a", "b", "c", "d"]

def cut_capacity(S):
    return sum(c for u, v, c in arcs if u in S and v not in S)    # only arcs from S to T count

cuts = [{"s", *extra} for k in range(len(inner) + 1) for extra in combinations(inner, k)]
best = min(cuts, key=cut_capacity)
print(len(cuts), sorted(best), cut_capacity(best))                # 16 ['c', 's'] 19
print(sorted(cut_capacity(S) for S in cuts))
# [19, 20, 20, 20, 21, 24, 26, 27, 29, 30, 30, 30, 32, 32, 36, 40]

Consequences.

Menger's theorem (8.3): with capacity 1 on every edge, a maximum flow is a set of edge-disjoint paths and a minimum cut is a smallest separating edge set.
König's and Hall's theorems: in the matching network, a minimum cut corresponds to a minimum vertex cover, and a cut smaller than |X| exhibits a set violating Hall's condition.
Applications: network reliability (minimum number of links whose failure separates two sites), image segmentation (separating foreground from background pixels with a minimum cut), baseball elimination, and airline scheduling.

Key takeaways

A cut separates s from t, and its capacity counts only arcs from the s side to the t side.
Every flow is at most every cut (weak duality), and the maximum flow equals the minimum cut.
When no augmenting path remains, the vertices reachable from s in the residual graph form a minimum cut.
The theorem certifies optimality, and it implies Menger's, König's and Hall's theorems.

Practice

(Beginner) Compute the capacity of the cuts S = {s, a, b} and S = {s, c, d} in the example network, and check that both are at least 19.

(Intermediate) Prove weak duality carefully: show that for every cut (S, T), the value |f| equals the flow from S to T minus the flow from T to S. Hint: add up the conservation equations of all vertices in S. Arcs with both ends in S cancel.

(Interview) Two data centers are connected through a mesh of routers and links. Management asks for the smallest number of links whose simultaneous failure would cut them off from each other, and for the actual list of links. How do you compute both? Hint: give every link capacity 1 (an undirected link becomes two opposite arcs) and run max flow between the two data centers. The flow value is the number, and the arcs leaving the residual-reachable set are the list.

Step	Finalize	`B`	`C`	`D`	`E`	`F`
0		∞	∞	∞	∞	∞
1	`A`	4	2	∞	∞	∞
2	`C`	3	2	∞	12	∞
3	`B`	3	2	8	12	∞
4	`D`	3	2	8	10	14
5	`E`	3	2	8	10	13
6	`F`	3	2	8	10	13

Step	Finalize	`B`	`C`	`D`	`E`	`F`
0		∞	∞	∞	∞	∞
1	`A`	4	2	∞	∞	∞
2	`C`	3	2	∞	12	∞
3	`B`	3	2	8	12	∞
4	`D`	3	2	8	10	14
5	`E`	3	2	8	10	13
6	`F`	3	2	8	10	13

Step	Finalize	`B`	`C`	`D`	`E`	`F`
0		∞	∞	∞	∞	∞
1	`A`	4	2	∞	∞	∞
2	`C`	3	2	∞	12	∞
3	`B`	3	2	8	12	∞
4	`D`	3	2	8	10	14
5	`E`	3	2	8	10	13
6	`F`	3	2	8	10	13

Step	Finalize	`B`	`C`	`D`	`E`	`F`
0		∞	∞	∞	∞	∞
1	`A`	4	2	∞	∞	∞
2	`C`	3	2	∞	12	∞
3	`B`	3	2	8	12	∞
4	`D`	3	2	8	10	14
5	`E`	3	2	8	10	13
6	`F`	3	2	8	10	13

Step	Finalize	`B`	`C`	`D`	`E`	`F`
0		∞	∞	∞	∞	∞
1	`A`	4	2	∞	∞	∞
2	`C`	3	2	∞	12	∞
3	`B`	3	2	8	12	∞
4	`D`	3	2	8	10	14
5	`E`	3	2	8	10	13
6	`F`	3	2	8	10	13

Step	Finalize	`B`	`C`	`D`	`E`	`F`
0		∞	∞	∞	∞	∞
1	`A`	4	2	∞	∞	∞
2	`C`	3	2	∞	12	∞
3	`B`	3	2	8	12	∞
4	`D`	3	2	8	10	14
5	`E`	3	2	8	10	13
6	`F`	3	2	8	10	13