Chapter 1: Vertex Coloring

Colorings and Chromatic Number

A coloring of a graph \(G\) is an assignment of colors to the vertices of \(G\) such that no two adjacent vertices receive the same color. More precisely, a \(k\)-coloring of \(G\) is a function \(\phi: V(G) \to [k]\) satisfying \(\phi(u) \neq \phi(v)\) for every edge \(uv \in E(G)\). Since every graph \(G\) trivially admits a \(|V(G)|\)-coloring — simply assign each vertex its own color — the interesting question is how few colors suffice.

The chromatic number of \(G\), denoted \(\chi(G)\), is the minimum \(k\) such that \(G\) has a \(k\)-coloring. This single invariant encodes a remarkable amount of structural information about a graph, and computing it is one of the central problems in combinatorics.

Why study coloring? First, it is a foundational problem in graph labeling: we study functions on \(V(G)\) subject to constraints imposed by the edge structure. Second, it is a foundational problem in graph decomposition: a \(k\)-coloring partitions \(V(G)\) into \(k\) independent sets. Third, coloring has deep applications to scheduling, frequency assignment in wireless networks, register allocation in compilers, and distributed computing. Yet despite its ubiquity, coloring is computationally hard: Karp proved in 1972 that deciding whether a graph is \(k\)-colorable is NP-complete for every \(k \geq 3\), and this remains true even for planar graphs when \(k = 3\). Any constant-factor approximation of \(\chi(G)\) is also NP-hard.

A graph being an independent set is equivalent to being 1-colorable. A graph being bipartite is equivalent to being 2-colorable, and a classical result states that \(G\) is 2-colorable if and only if \(G\) contains no odd cycle. Moreover, there is a polynomial-time algorithm to test 2-colorability (simply run BFS and check for odd cycles). The complexity barrier thus lies precisely at three colors.

Bounds on the Chromatic Number

The simplest upper bound comes from the greedy algorithm. Order the vertices of \(G\) arbitrarily as \(v_1, v_2, \ldots, v_n\). Color them in order, assigning each vertex the smallest color not used by its already-colored neighbors. Since each vertex has at most \(\Delta(G)\) neighbors, there is always a color available from the palette \(\{1, 2, \ldots, \Delta(G) + 1\}\). This gives the greedy upper bound:

where \(\Delta(G)\) denotes the maximum degree. For the lower bound, every clique requires all its vertices to receive distinct colors, so \(\chi(G) \geq \omega(G)\), where \(\omega(G)\) is the clique number — the size of the largest complete subgraph.

Can we improve the greedy bound? For complete graphs, \(\chi(K_n) = n = \Delta(K_n) + 1\), so the bound is tight. Even for connected non-complete graphs, odd cycles show that equality can hold: \(\chi(C_{2k+1}) = 3 = \Delta(C_{2k+1}) + 1\). The remarkable content of Brooks’ theorem is that these are the only obstructions.

Brooks’ Theorem

This theorem admits at least eight fundamentally different proofs, as surveyed by Cranston and Rabern (2014) in their article Brooks’ Theorem and Beyond. These include proofs via greedy coloring with a clever vertex ordering, Kempe chains, list coloring, the Alon–Tarsi theorem, kernel perfection, and potential methods. We present the approach via greedy coloring and structural reductions, which is arguably the most direct.

Proof via Greedy Coloring and Reductions

The strategy is to show that if \(G\) is a minimum counterexample — a connected graph that is neither complete nor an odd cycle, yet satisfies \(\chi(G) = \Delta(G) + 1\) — then we can always find a vertex ordering for which the greedy algorithm uses only \(\Delta(G)\) colors.

The greedy algorithm fails at a vertex \(v\) (that is, requires the \((\Delta(G)+1)\)-th color) only when \(v\) has exactly \(\Delta(G)\) earlier neighbors in the ordering, each colored with a different color from \(\{1, \ldots, \Delta(G)\}\). The idea is to find an ordering where this disaster cannot happen.

First Reduction: Cutvertex. Suppose \(G\) has a cutvertex \(v\) separating \(G\) into subgraphs \(G_1\) and \(G_2\) (each containing \(v\)). By minimality, each \(G_i\) has a \(\Delta\)-coloring \(\phi_i\) (provided neither is complete or an odd cycle of the right degree). Permute the colors in \(\phi_2\) so that \(\phi_1(v) = \phi_2(v)\), and the colorings glue together into a \(\Delta\)-coloring of \(G\).

Second Reduction: 2-vertex cutset. If \(G\) has a cutset \(\{u, v\}\) separating \(G\) into \(G_1, G_2\), we try the same trick. If \(uv \in E(G)\), we can permute colors to match on both \(u\) and \(v\). If \(uv \notin E(G)\), we add the edge \(uv\) to both \(G_1\) and \(G_2\) (checking that this doesn’t increase the maximum degree or create a forbidden subgraph) and apply induction.

The Finishing Blow. After these reductions, we may assume \(G\) is 3-connected. Now we use the structure of a depth-first search tree. Fix a root \(r\) and take a DFS ordering, then reverse it. In this reversed ordering, every vertex except the root has a neighbor appearing later — specifically, its parent in the DFS tree. So every vertex except the last (which is \(r\)) has at most \(\Delta(G) - 1\) earlier neighbors, and the greedy algorithm succeeds at these vertices using \(\Delta(G)\) colors.

The only vertex that might fail is the root \(r\). If \(\deg(r) \leq \Delta(G) - 1\), there is room. Otherwise, since \(G\) is not \(K_{\Delta+1}\), the root \(r\) has two non-adjacent neighbors \(x\) and \(y\). Make \(x\) and \(y\) the first two vertices in the ordering (so they receive the same color), then run greedy from the reversed DFS order after that. When the algorithm reaches \(r\), two of its neighbors share a color, so at most \(\Delta(G) - 1\) distinct colors appear among its neighbors, and \(r\) can be colored.

An elegant alternative proof uses the following structural lemma. A clique cutset of a graph \(G\) is a clique \(X\) in \(G\) such that \(G - X\) is disconnected. A \(k\)-critical graph — one satisfying \(\chi(G) = k\) but \(\chi(H) < k\) for every proper subgraph \(H\) — can have no clique cutset (if it did, we could color each piece separately and match colors on the clique). Every simple graph with no clique cutset that is neither complete nor a cycle must contain three vertices \(u, v, w\) with \(uw, vw \in E(G)\), \(uv \notin E(G)\), and \(G - u - v\) connected. Ordering the vertices so that \(u, v\) come first (receiving the same color), \(w\) comes last, and the intermediate vertices follow a connected ordering of \(G - u - v\), yields a greedy \(\Delta\)-coloring.

Beyond Brooks’ Theorem

Brooks’ theorem tells us that \(\chi(G) \leq \Delta(G)\) unless \(G\) contains a large clique. A natural question is: can we do even better when the graph has additional structure?

Reed’s Conjecture (1998) proposes that \(\chi(G) \leq \lceil (\Delta(G) + 1 + \omega(G))/2 \rceil\) for every graph \(G\). This would interpolate between the trivial upper bound \(\Delta(G) + 1\) and the trivial lower bound \(\omega(G)\). The conjecture remains open, but substantial progress has been made for large \(\Delta\).

Triangle-free graphs. Johansson (1996) proved the breakthrough result that if \(G\) is triangle-free, then \(\chi(G) \leq O(\Delta(G)/\ln \Delta(G))\). Molloy (2019) sharpened this to \(\chi(G) \leq (1 + o(1))\Delta(G)/\ln \Delta(G)\), which is tight up to the leading constant.

Bounded clique number. For fixed \(r\), Johansson (1999) showed that graphs with \(\omega(G) \leq r\) satisfy \(\chi(G) \leq O(\Delta/\ln \Delta \cdot \ln \ln \Delta)\). Bonamy, Kelly, Nelson, and Postle (2022) proved the more general bound \(\chi(G) \leq O(\Delta \sqrt{\ln \omega / \ln \Delta})\), from which it follows that if \(\omega(G) \leq \Delta(G)^{1/(192k)^2}\), then \(\chi(G) \leq \Delta(G)/k\). Ramsey-theoretic constructions show this cannot extend beyond \(\omega \approx \Delta^{2/(k-1)}\).

Critical Graphs and Degeneracy

A graph \(G\) is \(k\)-critical if \(\chi(G) = k\) but \(\chi(H) < k\) for every proper subgraph \(H\). Critical graphs are the minimal obstructions to \((k-1)\)-colorability, and understanding their structure is central to coloring theory.

Every vertex in a \(k\)-critical graph has degree at least \(k - 1\): if some vertex \(v\) had degree at most \(k - 2\), then \(G - v\) would have a \((k-1)\)-coloring that extends to \(v\), contradicting criticality. This observation connects to the notion of degeneracy: a graph is \(d\)-degenerate if every nonempty subgraph has a vertex of degree at most \(d\). Since a \(d\)-degenerate graph cannot contain a \((d+2)\)-critical subgraph, every \(d\)-degenerate graph is \((d+1)\)-colorable. Forests are 1-degenerate (hence 2-colorable), simple planar graphs are 5-degenerate (hence 6-colorable), and planar graphs with no \(K_4\)-minor are 2-degenerate (hence 3-colorable).

The Hajós Construction

Given two graphs \(H_1, H_2\) with \(\chi(H_i) \geq k\), the Hajós construction produces a new graph \(G\) that also has \(\chi(G) \geq k\). Specifically, choose edges \(x y_1 \in E(H_1)\) and \(x y_2 \in E(H_2)\) sharing an endpoint \(x\), form \(G = (H_1 \cup H_2) - \{xy_1, xy_2\} + y_1 y_2\), and observe that any \((k-1)\)-coloring of \(G\) would force \(y_1, y_2\) to have the same color (since they play the role of \(x\) in each piece), contradicting the new edge \(y_1 y_2\).

This is a beautiful theoretical characterization, though it does not yield an efficient algorithm (the construction can be exponentially large).

List Coloring and Thomassen’s Theorem

A more refined notion of coloring assigns each vertex a list of permissible colors. A graph \(G\) is \(k\)-choosable (or \(k\)-list-colorable) if for every assignment of lists \(L(v)\) with \(|L(v)| \geq k\), there is a proper coloring \(\phi\) with \(\phi(v) \in L(v)\) for all \(v\). The list chromatic number \(\chi_\ell(G)\) is the minimum \(k\) for which \(G\) is \(k\)-choosable.

Clearly \(\chi_\ell(G) \geq \chi(G)\), since ordinary coloring is the special case where all lists are \([k]\). But the inequality can be strict: the complete bipartite graph \(K_{3,3}\) satisfies \(\chi(K_{3,3}) = 2\) but \(\chi_\ell(K_{3,3}) = 3\).

Thomassen’s proof is a gem of structural induction. The key insight is to prove a stronger statement: if \(G\) is a planar graph with outer face bounded by a cycle \(C = v_1 v_2 \cdots v_k\), and if the vertices of \(C\) are given lists of size 3 (except for two adjacent vertices \(v_1, v_2\) with lists of size 1 — that is, pre-colored), and all interior vertices have lists of size 5, then \(G\) has a list coloring.

The proof proceeds by induction on \(|V(G)|\). One finds either a chord of the outer cycle (splitting the graph into two smaller pieces) or a vertex on the outer cycle with a neighbor in the interior, and applies the inductive hypothesis after careful case analysis. The pre-coloring of two adjacent outer vertices is crucial for making the induction work — it is an instance of the general phenomenon that proving a stronger statement can make an induction easier.

Thomassen’s theorem is best possible in the sense that there exist planar graphs that are not 4-choosable (the first example was found by Voigt in 1993). Whether every planar graph is 4-colorable from lists of size 4 when the lists are “generic” remains an active area of research.

Chapter 2: Edge Coloring

Edge Colorings and the Chromatic Index

An edge coloring of a graph \(G\) is an assignment of colors to the edges of \(G\) such that no two edges sharing an endpoint receive the same color. The chromatic index (or edge chromatic number) \(\chi'(G)\) is the minimum number of colors needed.

Edge coloring is intimately connected to vertex coloring through the line graph: define \(L(G)\) to be the graph with vertex set \(E(G)\), where two edges of \(G\) are adjacent in \(L(G)\) if they share an endpoint. Then \(\chi'(G) = \chi(L(G))\).

The lower bound holds because the edges incident to any maximum-degree vertex must all receive different colors. The upper bound comes from applying the greedy bound to \(L(G)\), since \(\Delta(L(G)) \leq 2\Delta(G) - 2\).

König’s Theorem

This theorem has two elegant proofs.

First proof (via Hall’s theorem). It suffices to prove the result when \(G\) is \(\Delta\)-regular, since any bipartite graph is a subgraph of a \(\Delta\)-regular bipartite graph. By Hall’s marriage theorem (double-counting shows every subset \(S\) of one part satisfies \(|N(S)| \geq |S|\)), a perfect matching \(M\) exists. Color \(M\) with color \(\Delta\), and apply induction to \(G - M\).

Second proof (via Kempe chains). Proceed by induction on \(|E(G)|\). Given an edge \(e = uv\) and a \(\Delta\)-edge-coloring \(\phi\) of \(G - e\), both \(u\) and \(v\) have missing colors (colors not used at that vertex). If their sets of missing colors intersect, we are done — assign the shared color to \(e\).

If no color is missing at both endpoints, choose \(a \in \bar\phi(u)\), \(b \in \bar\phi(v)\) (where \(\bar\phi(v)\) denotes the set of colors missing at \(v\)). Consider the maximal path of alternating \(a\)- and \(b\)-colored edges starting at \(u\) — this is the \((a,b)\)-Kempe chain at \(u\). If \(v\) lies on this path, then the path has even length, and together with \(e\) it forms an odd cycle — contradicting bipartiteness. If \(v\) is not on the path, swapping \(a\) and \(b\) along it makes \(b\) available at both \(u\) and \(v\), allowing us to color \(e\).

Vizing’s Theorem

This theorem says that the chromatic index of any simple graph is either \(\Delta(G)\) or \(\Delta(G) + 1\). A graph is called class 1 if \(\chi'(G) = \Delta(G)\) and class 2 if \(\chi'(G) = \Delta(G) + 1\). Deciding which class a graph belongs to is NP-complete.

The Vizing Fan Argument

The proof introduces the Vizing fan, one of the most important technical tools in edge coloring theory. Suppose \(e = v_0 v_1 \in E(G)\) and \(\phi\) is a \(k\)-edge-coloring of \(G - e\) (with \(k \geq \Delta + 1\)). A Vizing fan with respect to \(e\), \(v_0\), and \(\phi\) is a sequence \(T = (v_0, e_1, v_1, e_2, v_2, \ldots, e_n, v_n)\) where:

• The vertices \(v_0, v_1, \ldots, v_n\) are all distinct,
• Each \(e_j = v_j v_0\) is an edge,
• For each \(j \geq 2\), the color \(\phi(e_j)\) is missing at some earlier vertex \(v_i\) with \(i < j\).

The crucial disjoint missing colors lemma states: if \(G\) has no \(k\)-edge-coloring (with \(k \geq \Delta + 1\)), and \(T\) is a Vizing fan with respect to some edge \(e\), then the sets of missing colors at distinct fan vertices are pairwise disjoint.

The proof of this lemma proceeds by contradiction, considering three cases for the first pair \((i, j)\) of fan vertices sharing a missing color \(\alpha\):

• Case 1: \(i = 0, j = 1\). Color \(\alpha\) is missing at both \(v_0\) and \(v_1\), so we can color \(e\) with \(\alpha\) — contradiction.
• Case 2: \(i = 0, j > 1\). Let \(\beta = \phi(v_0 v_j)\). Since \(T\) is a Vizing fan, \(\beta\) is missing at some \(v_{j'}\) with \(j' < j\). Switch the \((\alpha, \beta)\)-Kempe chain at \(v_0\) to obtain a new coloring in which \(\beta\) is missing at both \(v_0\) and \(v_{j'}\), giving a shorter fan — contradicting minimality.
• Case 3: \(i > 0\). Let \(\beta\) be any color missing at \(v_0\). Switch the \((\alpha, \beta)\)-Kempe chain at \(v_i\). If \(v_0\) is not on this chain, \(\beta\) becomes missing at both \(v_0\) and \(v_i\) — contradiction. If \(v_0\) is on the chain, switch the \((\alpha, \beta)\)-chain at \(v_j\) instead (which cannot contain \(v_0\) since the chain at \(v_i\) already does), obtaining the same contradiction.

Given the disjoint missing colors lemma, take a maximal Vizing fan. Since the fan vertices have pairwise disjoint sets of missing colors, and each vertex has at least one missing color (because \(k \geq \Delta + 1\)), the fan can include at most \(k\) vertices. But since the fan is maximal, every color missing at \(v_0\) appears as \(\phi(e_j)\) for some fan edge, meaning \(v_0\) has at most \(n\) missing colors while the fan has \(n + 1\) vertices with disjoint missing color sets within a palette of \(k\) colors. This forces \(k \leq \Delta\), contradicting \(k \geq \Delta + 1\).

List Edge Coloring and Multigraphs

The list chromatic index \(\chi_\ell'(G)\) is defined analogously to the list chromatic number, but for edges. The List Edge Coloring Conjecture (attributed independently to several researchers) asserts that \(\chi_\ell'(G) = \chi'(G)\) for every graph \(G\). This remains one of the major open problems in graph theory. It is known to hold for bipartite graphs (Galvin, 1995).

For multigraphs (graphs with parallel edges), the situation is more complex. The trivial lower bound becomes \(\chi'(G) \geq \max(\Delta(G), \mu(G) \cdot \lceil \Delta(G)/\lfloor |V(G)|/2 \rfloor \rceil)\), where \(\mu(G)\) is the maximum edge multiplicity. Shannon (1949) proved that \(\chi'(G) \leq \lfloor 3\Delta(G)/2 \rfloor\) for multigraphs. Vizing extended his theorem to show \(\chi'(G) \leq \Delta(G) + \mu(G)\) for multigraphs.

Chapter 3: Planar Graphs, Surfaces, and Discharging

Coloring Planar Graphs

The Four Color Theorem — that every planar graph is 4-colorable — is one of the most celebrated results in mathematics. First conjectured by Guthrie in 1852 and proved by Appel and Haken in 1976 with extensive computer assistance (later simplified and verified by Robertson, Sanders, Seymour, and Thomas in 1997), it remains the only major theorem whose proof requires a computer.

For our purposes, the key structural observation is that a minimum counterexample to the Four Color Theorem must be a simple planar triangulation that is 4-connected. The triangulation requirement follows because a 5-critical plane graph is 2-connected, and any non-triangular face of degree \(\geq 4\) can be split by identifying two non-adjacent vertices on its boundary — producing a smaller counterexample.

Thomassen’s theorem (Chapter 1) gives the best result achievable by purely structural methods: every planar graph is 5-choosable. The gap between 4-colorability and 5-choosability is genuine — there exist planar graphs that are not 4-choosable.

The Discharging Method

The method works as follows:

1. Assign an initial charge \(\text{ch}_0(x)\) to each vertex and face \(x\), chosen so that the total charge is negative (typically \(-12\) for connected graphs, arising from Euler’s formula).
2. Redistribute charge according to specified discharging rules, which move charge between vertices and faces without changing the total.
3. Show that under the assumption that the desired structural property fails, all final charges are nonnegative — contradicting the negative total.

Common Discharging Setups

Three standard initial charge assignments arise from different ways of expressing Euler’s formula:

Vertex-centric setup: \(\text{ch}_0(v) = \deg(v) - 6\) for vertices, \(\text{ch}_0(f) = 2(|f| - 3)\) for faces. Total: \(\leq -12\). Best for graphs with large minimum degree.

Face-centric setup: \(\text{ch}_0(v) = 2(\deg(v) - 3)\) for vertices, \(\text{ch}_0(f) = |f| - 6\) for faces. Total: \(-12\). Best for cubic (3-regular) plane graphs.

Balanced setup: \(\text{ch}_0(v) = \deg(v) - 4\) for vertices, \(\text{ch}_0(f) = |f| - 4\) for faces. Total: \(-8\). Best for triangle-free graphs or graphs with restricted triangles.

A Discharging Example

As an illustration, consider the following result: every planar graph with no 4-to-9-cycles is 3-colorable. The proof uses discharging (face-centric setup) to show that every plane graph with \(\delta(G) \geq 3\) must contain either two adjacent triangles, a face of size between 4 and 9, or a 10-face all of whose incident vertices have degree 3. If there are no 4-to-9-cycles, the third outcome must hold, and one can delete the vertices of this 10-face, color by induction, and extend (since even cycles are 2-list-colorable).

Surfaces

A surface is a closed, compact, connected 2-dimensional manifold. The classical classification theorem states that every surface is homeomorphic to either the sphere with \(g\) handles attached (an orientable surface \(\Sigma_g\) of genus \(g\)) or the sphere with \(k\) crosscaps attached (a non-orientable surface \(N_k\) of non-orientable genus \(k\)).

The sphere is \(\Sigma_0\), the torus is \(\Sigma_1\), the projective plane is \(N_1\), and the Klein bottle is \(N_2\).

Three operations build all surfaces from the sphere:

• Connected sum: remove a disk from each of two surfaces and glue along the boundary circles.
• Adding a handle: remove two disks and identify their boundaries with the same orientation. This increases the orientable genus by 1.
• Adding a crosscap: remove a disk and identify antipodal points of its boundary. This converts an orientable surface to a non-orientable one.

Euler’s Formula for Surfaces

This yields edge bounds: a simple graph on \(\Sigma_g\) satisfies \(|E| \leq 3|V| + 6(g - 1)\) (when \(|V| \geq 3\)). Combined with arguments about critical graphs, this implies that the number of \(k\)-critical graphs embeddable on any fixed surface is finite (for \(k \geq 8\) by elementary counting, and for \(k \geq 6\) by deep work of Thomassen).

Coloring Graphs on Surfaces

The Heawood bound gives \(\chi(\Sigma_g) \leq \lfloor (7 + \sqrt{1 + 48g})/2 \rfloor\) for \(g \geq 1\). The Ringel–Youngs theorem (1968) shows this bound is tight for every surface except the sphere (where the bound gives 4, but the truth is also 4 by the Four Color Theorem — though proving tightness required much deeper methods).

Thomassen observed that 5-choosability results for planar graphs extend: for each surface, there are only finitely many obstructions to 5-colorability, and these can be characterized by short non-contractible cycles. Specifically, if \(G\) embeds in \(\Sigma_g\) and is not 5-colorable, then \(G\) has a non-contractible cycle of bounded length (depending on \(g\)).

Chapter 4: Graph Minors

Minors and Contractions

Graph minor theory, largely developed by Robertson and Seymour in their monumental series of over twenty papers, provides some of the deepest structural results in all of graph theory.

Given an edge \(e = uv\) in a graph \(G\), the deletion \(G \setminus e\) removes the edge while keeping all vertices, and the contraction \(G / e\) identifies \(u\) and \(v\) into a single vertex, removing \(e\) and any resulting parallel edges or loops. A graph \(H\) is a minor of \(G\) if \(H\) can be obtained from a subgraph of \(G\) by contracting edges. Equivalently, \(G\) has an \(H\)-minor if there exist vertex-disjoint connected subgraphs (called branch sets) \(T_v\) in \(G\), one for each \(v \in V(H)\), such that for every edge \(uv \in E(H)\), there is an edge in \(G\) between \(T_u\) and \(T_v\).

A class of graphs \(\mathcal{G}\) is minor-closed if every minor of a graph in \(\mathcal{G}\) also belongs to \(\mathcal{G}\). Many natural graph classes are minor-closed: planar graphs, forests, graphs embeddable on any fixed surface, apex graphs (graphs with a vertex whose removal leaves a planar graph), and for each \(k\), the class of graphs with no path of length \(> k\) or no \(k\) vertex-disjoint cycles.

The Graph Minor Theorem

Equivalently: in any infinite sequence of graphs, some graph is a minor of a later one. This theorem took Robertson and Seymour over twenty years and twenty papers to prove. It has remarkable consequences:

• There are only countably many minor-closed graph classes.
• For each minor-closed class, the membership testing problem is decidable.
• There is an \(O(n^3)\) algorithm for testing whether a fixed graph \(H\) is a minor of an input graph \(G\).

The excluded minors are known explicitly only for a few classes: planar graphs (\(K_5\) and \(K_{3,3}\), by Kuratowski’s theorem), graphs of treewidth \(\leq k\) for small \(k\), and a handful of others. The set of excluded minors for linklessly embeddable graphs has been determined (the Petersen family), and the projective-planar graphs have 32 excluded minors.

Edge Density in Minor-Closed Classes

How many edges can a graph in a minor-closed class have?

The proof is a beautiful induction argument. In a minimum counterexample \(G\), take a minimum-degree vertex \(v\) and look at the subgraph \(H\) induced by its neighbors. Since \(H\) has no \(K_{m-1}\)-minor, by induction \(H\) has a vertex \(w\) of degree at most \(2^m - 2\) in \(H\). Contracting the edge \(vw\) and simplifying produces a smaller counterexample.

More precisely, let \(h_t(n)\) denote the maximum number of edges in a simple \(n\)-vertex graph with no \(K_t\)-minor. Then:

• \(h_t(n) \geq (t-2)n - \binom{t-1}{2}\) for all \(n \geq t \geq 2\).
• Equality holds for \(t \in \{2, 3, 4, 5, 6, 7\}\) (Mader).
• For large \(t\), Thomason showed \(h_t(n) = (\alpha + o(1)) t\sqrt{\ln t} \cdot n\) for \(\alpha \approx 0.319\).

As special cases: no \(K_3\)-minor means forest (\(|E| \leq |V| - 1\)); no \(K_4\)-minor gives \(|E| \leq 2|V| - 3\); no \(K_5\)-minor gives \(|E| \leq 3|V| - 6\) (the planar bound).

A key corollary is that every proper minor-closed class has linear edge density — there exists a constant \(c_\mathcal{G}\) such that every graph in \(\mathcal{G}\) satisfies \(|E| \leq c_\mathcal{G} |V|\).

Tree Decompositions and Treewidth

How “tree-like” is a graph? This is formalized by the notion of treewidth.

A tree decomposition of a graph \(G\) is a pair \((T, \mathscr{V})\) where \(T\) is a tree and \(\mathscr{V} = (V_t)_{t \in V(T)}\) is a family of subsets of \(V(G)\) (called bags) satisfying:

1. \(V(G) = \bigcup_{t \in T} V_t\),
2. For every edge \(uv \in E(G)\), there exists \(t \in V(T)\) with \(u, v \in V_t\),
3. For every vertex \(v \in V(G)\), the set \(\{t \in V(T) : v \in V_t\}\) induces a connected subtree of \(T\).

The width of the decomposition is \(\max_{t \in V(T)} |V_t| - 1\), and the treewidth of \(G\) is the minimum width over all tree decompositions.

Trees have treewidth \(\leq 1\). Series-parallel graphs (equivalently, graphs with no \(K_4\)-minor) have treewidth \(\leq 2\). Treewidth is minor-monotone: if \(H\) is a minor of \(G\), then \(\text{tw}(H) \leq \text{tw}(G)\).

The Grid Theorem

Since every planar graph is a minor of a sufficiently large grid (and the \(k \times k\) grid has treewidth \(k\)), this gives a qualitative characterization: the minor-closed classes of bounded treewidth are precisely those that exclude some planar graph.

The Erdős–Pósa Theorem

The grid theorem connects to a classical result about packing and covering cycles.

The proof uses tree decompositions: if \(G\) has no \(k\) vertex-disjoint cycles, its treewidth is bounded, so it has a tree decomposition of bounded width. The Helly property of subtrees of a tree then produces a small hitting set.

Hadwiger’s Conjecture

The deepest open problem connecting minors and coloring is:

This conjecture has been verified for \(t \leq 5\) (the case \(t = 4\) is equivalent to the Four Color Theorem, by Wagner’s equivalence; \(t = 5\) was proved by Robertson, Seymour, and Thomas). For general \(t\), the best known bound is \(\chi(G) = O(t \sqrt{\log t})\) for \(K_t\)-minor-free graphs (Kostochka and Thomason, independently). Wagner’s theorem gives a structural characterization for \(t = 4\): every graph with no \(K_5\)-minor can be obtained by clique-sums of planar graphs and copies of the Wagner graph \(V_8\).

Chapter 5: Extremal Graph Theory

Turán’s Theorem

Extremal graph theory asks: what is the maximum number of edges in a graph on \(n\) vertices that avoids a particular subgraph \(H\)? The Turán number \(\text{ex}(n, H)\) is this maximum, and a graph achieving it is called extremal.

The foundational result, predating the field’s formal creation, is Mantel’s theorem (1907): the maximum number of edges in a triangle-free graph on \(n\) vertices is \(\lceil n/2 \rceil \lfloor n/2 \rfloor\), achieved uniquely by the complete bipartite graph \(K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor}\).

Turán generalized this to all complete graphs. The Turán graph \(T^{r-1}(n)\) is the unique complete \((r-1)\)-partite graph on \(n\) vertices whose part sizes differ by at most 1.

Two proofs illuminate different aspects of the result.

First proof (by induction). A maximal \(K_r\)-free graph contains \(K_{r-1}\); remove it, apply induction to the remainder, and verify that each vertex in the remainder has exactly \(r - 2\) neighbors in the clique.

Second proof (by vertex duplication). Show that the extremal graph must be complete multipartite: if non-adjacency is not an equivalence relation — that is, if there exist vertices \(y_1, x, y_2\) with \(y_1 x, y_2 x \notin E\) but \(y_1 y_2 \in E\) — then replacing a lower-degree vertex by a duplicate of a higher-degree vertex produces a \(K_r\)-free graph with more edges, contradicting extremality.

Ramsey Theory

Ramsey theory asks: can we always find order in chaos? Specifically, does every sufficiently large graph necessarily contain either a large clique or a large independent set?

The Ramsey number \(R(k)\) is the minimum such \(n\) for \(r = k\). The proof gives the upper bound \(R(k) \leq 2^{2k-3}\): iteratively extract vertices, building up a sequence where each new vertex is either adjacent to all remaining vertices in a large subset or to none, then apply pigeonhole.

More generally, the Ramsey number \(R(k, \ell)\) is the minimum \(n\) such that every 2-coloring of the edges of \(K_n\) contains a red \(K_k\) or a blue \(K_\ell\). The recursion \(R(k, \ell) \leq R(k-1, \ell) + R(k, \ell-1)\) gives \(R(k, \ell) \leq \binom{k+\ell-2}{k-1}\), and hence \(R(k) \leq (1 + o(1)) 4^{k-1}/\sqrt{\pi k}\).

Exact values are known only for small cases: \(R(3) = 6\), \(R(4) = 18\). For \(R(5)\), only \(42 \leq R(5) \leq 48\) is known, and for \(R(6)\), \(102 \leq R(6) \leq 165\).

Ramsey’s theorem generalizes in two directions: to \(c\) colors (instead of 2) and to hypergraphs. The Infinite Ramsey Theorem states that for any finite coloring of the \(k\)-element subsets of an infinite set, there is an infinite monochromatic subset. The finite version follows by a compactness argument.

The Regularity Lemma

Szemerédi’s Regularity Lemma (1976) is one of the most powerful tools in combinatorics. It states that every large enough graph can be partitioned into a bounded number of parts such that the edges between most pairs of parts behave “pseudo-randomly.”

Given disjoint vertex sets \(X, Y\) in a graph \(G\), the density of the pair is \(d(X, Y) = \|X, Y\| / (|X| \cdot |Y|)\), where \(\|X, Y\|\) counts edges between \(X\) and \(Y\). The pair \((A, B)\) is \(\varepsilon\)-regular if for all \(X \subseteq A\) with \(|X| \geq \varepsilon |A|\) and \(Y \subseteq B\) with \(|Y| \geq \varepsilon |B|\), we have \(|d(X, Y) - d(A, B)| \leq \varepsilon\). Informally, the pair “looks like a random bipartite graph” at scale \(\varepsilon\).

The proof uses a potential function argument. Define \(q(\mathscr{P}) = \sum_{i < j} \frac{|V_i||V_j|}{|V|^2} d(V_i, V_j)^2\) for a partition \(\mathscr{P}\). This quantity lies in \([0, 1]\), increases under refinement (by Cauchy–Schwarz), and each step that resolves an irregular pair increases it by at least \(\varepsilon^5/2\). Hence the process terminates after at most \(2/\varepsilon^5\) steps.

The Erdős–Stone Theorem

The Erdős–Stone theorem determines the asymptotic behavior of Turán numbers for all non-bipartite graphs.

This is called the “fundamental theorem of extremal graph theory” because it shows that the chromatic number of \(H\) alone determines the growth rate of \(\text{ex}(n, H)\).

The proof via the regularity lemma is elegant. Apply the regularity lemma to \(G\) and form the regularity graph \(R\): its vertices are the parts \(V_1, \ldots, V_k\), and two parts are adjacent if they form an \(\varepsilon\)-regular pair of density \(\geq d\). If \(R\) contains \(K_r\), the Blow-Up Lemma lets us embed \(K_{s \ast r}\) into \(G\). If \(R\) does not contain \(K_r\), Turán’s theorem bounds \(|E(R)|\), and accounting for irregular pairs and low-density pairs gives \(|E(G)| \leq t_{r-1}(n) + \gamma n^2\), a contradiction.

The Blow-Up Lemma itself is proved by a greedy embedding argument: one embeds the vertices of \(H\) into \(G\) one by one, maintaining sets \(T_j^i\) of “candidate” vertices for each unembedded vertex \(v_j\). The \(\varepsilon\)-regularity condition ensures that these candidate sets remain large enough throughout the process (each has size at least \((d - \varepsilon)^{\Delta}|V_{r(j)}| \geq \frac{1}{2} d^\Delta \ell\), which is at least \(s\) by assumption).

An interesting consequence is the Removal Lemma: if a graph has \(o(n^{|V(H)|})\) copies of \(H\), it can be made \(H\)-free by removing \(o(n^2)\) edges. This in turn implies Roth’s theorem on arithmetic progressions.

Chapter 6: The Probabilistic Method

Ramsey Number Bounds

The probabilistic method, pioneered by Paul Erdős, proves the existence of combinatorial objects with desired properties by showing that a random construction succeeds with positive probability.

Upper bounds. The Erdős–Szekeres recursion gives \(R(k) \leq (1 + o(1)) 4^{k-1}/\sqrt{\pi k}\). Conlon (2009) improved this to \(R(k) \leq k^{-c \log k / \log \log k} \cdot 4^k\), and Sah (2020) further sharpened it to \(R(k) \leq k^{-c \log k} \cdot 4^k\). Yet the base of the exponent has stubbornly remained at 4.

The same bound holds for independent sets (by symmetry of \(p = 1/2\)). Choosing \(n \approx \frac{\sqrt{2} k}{e} \cdot 2^{k/2}\) makes each probability less than \(1/2\), so by the union bound the probability that either a \(K_k\) or \(\overline{K_k}\) exists is less than 1. Hence some graph on \(n\) vertices has neither — proving \(R(k) > n\).

The base of the exponential in the lower bound has also remained at \(\sqrt{2}\) since 1947.

Large Girth and Large Chromatic Number

Are there triangle-free graphs with arbitrarily large chromatic number? Yes — Tutte (1947), Zykov (1949), and Mycielski (1955) gave explicit constructions. The Mycielski construction takes a graph \(G\) on vertices \(\{v_1, \ldots, v_n\}\) and builds \(G'\) by adding a “shadow” \(v_i'\) for each vertex (adjacent to the neighbors of \(v_i\) but not to \(v_i\) itself) plus a universal vertex \(v_0\) adjacent to all shadows. If \(G\) is triangle-free, so is \(G'\), and \(\chi(G') = \chi(G) + 1\).

Erdős asked the deeper question: for every \(g\) and \(k\), is there a graph with girth \(\geq g\) and chromatic number \(\geq k\)? He answered it affirmatively using the probabilistic method.

The proof uses the random graph \(G(n, p)\) with \(p = n^{1/(2g-2) - 1}\), combined with an alteration step:

1. Few short cycles: The expected number of cycles of length \(\leq g-1\) is at most \(\sqrt{n}\) (by a calculation involving \(\mathbb{E}[\# C_\ell] = \frac{(n)_\ell}{2\ell} p^\ell\)). By Markov’s inequality, \(\Pr[\# C_{\leq g-1} \geq n/2] \leq 2(g-1)/\sqrt{n}\).

2. Small independence number: Setting \(k' = n/(2k)\), the probability that \(\alpha(G_{n,p}) \geq k'\) is at most \(1/n\) (using \((1-p) \leq e^{-p}\) and the choice of \(p\)).

3. Alteration: Since both bad events have probability less than \(1/2\) for large \(n\), there exists a graph \(G\) with \(\alpha(G) \leq n/(2k)\) and at most \(n/2\) short cycles. Delete one vertex from each short cycle to obtain \(G'\) with girth \(\geq g\) and at least \(n/2\) vertices. Then \(\chi(G') \geq |V(G')|/\alpha(G') \geq (n/2)/(n/(2k)) = k\).

Lovász (1968) gave the first explicit constructions of graphs with large girth and large chromatic number.

Bounded-Degree Ramsey

The proof combines the regularity lemma with the Blow-Up Lemma: apply regularity to a 2-coloring, find a monochromatic \(K_{\Delta+1}\) in the regularity graph (using that Ramsey numbers for complete graphs exist), then embed \(H\) into the dense regular pairs.

Chapter 7: Flows

Nowhere-Zero Flows

Flow theory, developed primarily by Tutte in the 1950s and 1960s, provides a powerful dual perspective on graph coloring. While coloring concerns proper vertex labelings, flows concern consistent edge labelings that satisfy a conservation law.

Let \(G\) be a graph and \(H\) a finite abelian group. An \(H\)-circulation is a function \(f: \vec{E}(G) \to H\) (where \(\vec{E}(G)\) is the set of directed edges — each edge appears twice, once in each direction) satisfying:

• Antisymmetry: \(f(e, x, y) = -f(e, y, x)\) for all edges \(e = xy\).
• Kirchhoff’s law: \(\sum_{e = xy \sim x} f(e, x, y) = 0\) for every vertex \(x\).

An \(H\)-circulation is called nowhere-zero (or an \(H\)-flow) if \(f(e, x, y) \neq 0\) for every directed edge. For integer-valued flows, a \(k\)-flow is a \(\mathbb{Z}\)-circulation \(f\) with \(0 < |f(e, x, y)| < k\) for all edges.

The fundamental insight is that the existence of nowhere-zero flows depends only on the group order, not the group structure.

The Flow Polynomial

This polynomial is computed via a contraction-deletion recurrence: if \(e\) is a non-loop edge, then \(P_G(x) = P_{G/e}(x) - P_{G \setminus e}(x)\). The proof establishes a bijection between \(H\)-flows of \(G/e\) and the disjoint union of \(H\)-flows of \(G\) and \(H\)-flows of \(G \setminus e\).

A crucial consequence: if a graph has an \(H\)-flow for some group of order \(k\), it has an \(H'\)-flow for every group of order \(k\). Furthermore, Tutte proved that \(G\) has a \(\mathbb{Z}_k\)-flow if and only if it has a \(k\)-flow (integer-valued). This means the flow number \(\varphi(G)\) — the minimum \(k\) such that \(G\) has a \(k\)-flow — is well-defined and does not depend on which group of that order we use.

Note that a graph with a bridge (cut-edge) admits no nowhere-zero flow of any kind, since Kirchhoff’s law forces the flow through a bridge to be zero.

Small Flows

2-flows. A graph has a 2-flow if and only if every vertex has even degree. This follows because a \(\mathbb{Z}_2\)-flow must assign the value 1 to every edge, and Kirchhoff’s law at each vertex requires an even number of incident edges.

3-flows and cubic graphs. A cubic graph has a 3-flow if and only if it is bipartite. In a \(\mathbb{Z}_3\)-flow on a cubic graph, Kirchhoff’s law forces all three edges at each vertex to have the same value (either all 1 or all 2). This creates a 2-coloring of the vertices.

4-flows. A graph has a 4-flow if and only if it is the union of two even subgraphs (since a \(\mathbb{Z}_2 \times \mathbb{Z}_2\)-flow decomposes into two \(\mathbb{Z}_2\)-circulations). For cubic graphs, having a 4-flow is equivalent to being 3-edge-colorable: in a \(\mathbb{Z}_2 \times \mathbb{Z}_2\)-flow on a cubic graph, the three nonzero elements \((1,0), (0,1), (1,1)\) play the role of three colors.

The proof uses Nash-Williams’ theorem that a 4-edge-connected graph has two edge-disjoint spanning trees \(T_1, T_2\). For each non-tree edge \(e \notin E(T_1)\), push a \((1,0)\)-flow around the fundamental cycle of \(e\) in \(T_1\). Edges of \(T_1\) that receive zero flow can then be given \((0,1)\)-flow via their fundamental cycles in \(T_2\), yielding a nowhere-zero \(\mathbb{Z}_2 \times \mathbb{Z}_2\)-flow.

Flow-Coloring Duality

For planar graphs, flows and colorings are dual to each other in a precise sense.

From coloring to flows. Given a \(k\)-coloring \(\phi\) of \(G\), define a flow on \(G^*\) by letting \(f(e^*) = \phi(u) - \phi(v)\), where \(u\) is the vertex on the “left” side of the edge \(e\) as viewed from the direction of \(e^*\). Since \(\phi\) is a proper coloring, \(f\) is nowhere-zero. Kirchhoff’s law holds because the flow around each face is a telescoping sum: \((\phi(w_1) - \phi(w_2)) + (\phi(w_2) - \phi(w_3)) + \cdots + (\phi(w_m) - \phi(w_1)) = 0\).

From flows to colorings. Given a \(k\)-flow \(f\) on \(G^*\), fix a spanning tree \(T\) of \(G\), color an arbitrary vertex with 1, and propagate colors along tree edges using the flow values. For a non-tree edge \(e = xy\), the fundamental cycle in \(T + e\) corresponds to a cut in \(G^*\), and the fact that \(f\) is nowhere-zero ensures \(\phi(x) \neq \phi(y)\).

This duality transforms planar coloring theorems into flow theorems:

• The Four Color Theorem is equivalent to: every bridgeless planar graph has a 4-flow.
• Grötzsch’s theorem (every triangle-free planar graph is 3-colorable) is equivalent to: every planar 4-edge-connected graph has a 3-flow.

Tutte’s Flow Conjectures

Tutte conjectured that these flow results extend beyond planar graphs:

5-Flow Conjecture (Tutte, 1954): Every bridgeless graph has a 5-flow.

4-Flow Conjecture (Tutte, 1966): Every bridgeless graph with no Petersen minor has a 4-flow.

3-Flow Conjecture (Tutte, 1972): Every 4-edge-connected graph has a 3-flow.

Progress on the Conjectures

The 5-Flow Conjecture has seen steady progress:

• Jaeger (1979) proved every bridgeless graph has an 8-flow (by constructing a \(\mathbb{Z}_2^3\)-flow).
• Seymour (1981) proved the celebrated 6-flow theorem: every bridgeless graph has a 6-flow. The proof constructs a \(\mathbb{Z}_2 \times \mathbb{Z}_3\)-flow using the notion of a 2-decomposition — a sequence of bridgeless graphs \(H_0 \subset H_1 \subset \cdots \subset H_k = G\) where \(H_0\) is Eulerian (even) and each step adds 1 or 2 edges. Every 3-edge-connected graph has such a decomposition, and from it one can build the required flow by layering \(\mathbb{Z}_2\)-flows on the even base and \(\mathbb{Z}_3\)-flows on fundamental cycles.

The 4-Flow Conjecture was proved for cubic graphs by Robertson, Sanders, Seymour, and Thomas (1998–2020+), which already generalizes the Four Color Theorem.

The 3-Flow Conjecture has been settled for highly connected graphs:

• Thomassen (2012): every 8-edge-connected graph has a 3-flow.
• Lovász, Thomassen, Wu, and Zhang (2013): every 6-edge-connected graph has a 3-flow.
• The conjecture that 5-edge-connectivity suffices (equivalent to the full conjecture, by Kochol 2001) remains open.

Chapter 8: Coloring Kneser Graphs and Topological Methods

Kneser Graphs

The Kneser graph \(K(n, k)\) has as its vertices all \(k\)-element subsets of \([n] = \{1, 2, \ldots, n\}\), with two vertices adjacent if and only if the corresponding subsets are disjoint. For example, \(K(5, 2)\) is the Petersen graph.

In 1955, Martin Kneser conjectured that \(\chi(K(n, k)) = n - 2k + 2\). The upper bound is easy: color a \(k\)-set \(S\) by the smallest element of \(S\) that lies in \(\{1, 2, \ldots, n - 2k + 2\}\) if such an element exists, and give all remaining sets a single extra color. This uses \(n - 2k + 2\) colors.

The lower bound — that \(n - 2k + 1\) colors do not suffice — resisted all combinatorial attacks for over two decades.

Lovász’s Topological Proof

Lovász’s proof was a thunderbolt: it used the Borsuk–Ulam theorem from algebraic topology, establishing that for any continuous map \(f: S^d \to \mathbb{R}^d\), there exists a point \(x\) with \(f(x) = f(-x)\). This was the birth of topological combinatorics — the use of topological tools to prove purely combinatorial results.

The proof associates a simplicial complex (the neighborhood complex \(\mathcal{N}(G)\)) to each graph \(G\), and shows that if this complex is “topologically \(k\)-connected,” then \(\chi(G) \geq k + 3\). For Kneser graphs, the neighborhood complex is sufficiently connected by a theorem of Bárány, and the Borsuk–Ulam theorem provides the topological connectivity.

Bárány gave a simpler proof using the Borsuk–Ulam theorem directly combined with a lemma of Gale. Greene (2002) simplified it further while remaining topological. In 2004, Matoušek gave the first purely combinatorial proof, completing a circle of ideas that began with topology.

The resolution of Kneser’s conjecture exemplifies a broader theme in graph theory: seemingly elementary combinatorial questions sometimes require deep tools from other areas of mathematics — topology, algebra, probability — and these connections often lead to new fields of research.