40.04.06 · combinatorics / graph-theory-core

Vertex Colouring: Brooks' Theorem and the Chromatic Polynomial

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 5 (vertex colouring, Brooks, perfect graphs, the strong perfect graph theorem stated) and Ch. 6 (list colouring) with the chromatic-polynomial / Tutte-polynomial threads; Bollobás 1998 *Modern Graph Theory* (Springer GTM 184) Ch. V (colouring) and Ch. X (the Tutte polynomial); the original sources Brooks 1941, Whitney 1932 (the broken-circuit theorem), Mycielski 1955, Chudnovsky-Robertson-Seymour-Thomas 2006 (the strong perfect graph theorem)

Intuition Beginner

Suppose you must hand out coloured badges so that no two people who dislike each other wear the same colour. Draw a dot for each person and a line between two people who clash. A colouring that obeys the rule gives each dot a colour with the one demand that two dots joined by a line never match. The smallest number of colours that lets you finish is the heart of this unit. For a map, the dots are countries, the lines join countries that share a border, and the colours keep neighbours apart.

How many colours do you really need? One cheap method always works: go through the dots in some order, and give each one the lowest-numbered colour not already used by a neighbour you have coloured. If every dot has at most $Δ$ lines touching it, then when you reach a dot it has seen at most $Δ$ used colours, so colour number $Δ + 1$ is always free. This greedy idea shows you can finish with at most one more colour than the busiest dot's line count.

That bound is often wasteful. A long chain of dots has busy middle dots, yet two colours suffice by alternating. So the true colour count depends on the shape, not just the worst dot. Brooks' theorem, the centrepiece here, says you can almost always save that one extra colour: the only shapes that genuinely need $Δ + 1$ are a fully-connected clump and an odd-length ring. Everything else fits in $Δ$ colours.

Visual Beginner

Picture a five-dot ring: dots $1, 2, 3, 4, 5$ placed in a pentagon, each joined to its two neighbours, and $5$ joined back to $1$ . Every dot touches exactly two lines, so the busiest-dot count is $2$ . You might hope two colours suffice, alternating around the ring. Going $1, 2, 3, 4, 5$ you colour them red, blue, red, blue, and then dot $5$ neighbours both dot $4$ (blue) and dot $1$ (red) — both colours are taken, so you need a third colour for dot $5$ .

The table records the clash: the odd ring forces a third colour even though no dot is busier than two.

dot	neighbours	colour
1	5, 2	red
2	1, 3	blue
3	2, 4	red
4	3, 5	blue
5	4, 1	green

An odd ring is one of the two shapes Brooks' theorem singles out as needing the extra colour. An even ring, by contrast, closes up cleanly on two colours.

Worked example Beginner

Colour the corners of a square where the two diagonals are also drawn in, using as few colours as possible. Label the corners $1, 2, 3, 4$ going around, with diagonals joining $1$ to $3$ and $2$ to $4$ . Now every corner is joined to every other corner: this is a fully-connected clump of four dots.

Step 1. Count the lines at one corner. Corner $1$ joins $2$ , $3$ , and $4$ , so it touches three lines. By symmetry every corner touches three lines, so the busiest-dot count is $3$ .

Step 2. Try three colours. Give corner $1$ red, corner $2$ blue, corner $3$ green. Corner $4$ is joined to all three of $1, 2, 3$ , so it sees red, blue, and green already. No colour among the three is free.

Step 3. Add a fourth colour. Corner $4$ gets yellow. Now all four corners have different colours and every line joins two unlike colours, so the rule holds. Four colours are needed and four suffice.

Step 4. Compare with the bound. The greedy method promised at most $3 + 1 = 4$ colours, and here we truly needed all four. A fully-connected clump of $n$ dots always needs exactly $n$ colours, one per dot.

What this tells us: a fully-connected clump is the worst case, using one colour per dot and hitting the greedy bound exactly. This is the other shape Brooks' theorem singles out. For everything that is neither a clump nor an odd ring, you can shave off that last colour.

Check your understanding Beginner

Formal definition Intermediate+

Let $G = (V, E)$ be a graph as defined in 40.04.01. A proper $k$ -colouring is a map $c : V \to {1, \dots, k}$ with $c (u) \neq = c (v)$ whenever ${u, v} \in E$ ^{[Diestel 2017 §5.1]}. Equivalently it is a partition of $V$ into $k$ colour classes $V_{1}, \dots, V_{k}$ , each an independent set (an edge-free vertex set). The chromatic number $χ (G)$ is the least $k$ for which a proper $k$ -colouring exists. A graph with $χ (G) \leq k$ is called $k$ -colourable; $χ (G) = k$ exactly means $k$ -colourable but not $(k - 1)$ -colourable.

Two lower-order invariants frame $χ$ . The clique number $ω (G)$ is the largest order of a complete subgraph, and the independence number $α (G)$ is the largest independent set. Every clique needs distinct colours, so $ω (G) \leq χ (G)$ ; and each colour class is independent of size at most $α (G)$ , so $χ (G) \geq n / α (G)$ .

For the upper bounds, order the vertices $v_{1}, \dots, v_{n}$ and colour greedily: give $v_{i}$ the least colour absent among its already-coloured neighbours. The colouring number $col (G)$ is $1$ plus the degeneracy $degen (G) = max_{H \subseteq G} δ (H)$ , the largest minimum degree over all subgraphs. A graph is $d$ -degenerate if every subgraph has a vertex of degree $\leq d$ ; repeatedly removing such a vertex yields a degeneracy ordering, and colouring in the reverse of that ordering shows $χ (G) \leq col (G) = degen (G) + 1$ . Since $degen (G) \leq Δ (G)$ , this refines the greedy bound $χ (G) \leq Δ (G) + 1$ .

The chromatic polynomial $P (G, k)$ is the number of proper colourings of $G$ with colours drawn from a palette of $k$ colours; it is a polynomial in $k$ of degree $n$ with integer coefficients, leading term $k^{n}$ , and $P (G, k) > 0$ exactly when $k \geq χ (G)$ . A perfect-elimination ordering is a vertex order in which each vertex's later neighbours form a clique; a graph admitting one is chordal, and for chordal graphs the greedy algorithm on the reverse order attains $χ = ω$ .

Counterexamples to common slips

The bound $ω \leq χ$ is not an equality. The five-cycle $C_{5}$ is triangle-free, so $ω (C_{5}) = 2$ , yet $χ (C_{5}) = 3$ . The gap between $ω$ and $χ$ can be arbitrarily large, as Mycielski's construction shows.
Greedy colouring is order-sensitive. The same graph can need $2$ colours under one vertex order and many more under a bad order; the path-like "crown" graphs make greedy use roughly $Δ/2$ colours when $2$ suffice. The degeneracy ordering is the order that controls the worst case.
$P (G, k)$ counts labelled colourings, not colourings up to permuting colours. For the single edge $K_{2}$ , $P (K_{2}, k) = k (k - 1)$ , not $k (k - 1) /2$ ; swapping the two colours gives a different counted colouring.
Brooks' exceptions are exactly two families. It is the complete graphs and the odd cycles that need $Δ + 1$ ; even cycles ( $Δ = 2$ , $χ = 2$ ) and the complete bipartite graphs ( $Δ$ large, $χ = 2$ ) obey $χ \leq Δ$ , so do not over-state the exception set.

Key theorem with proof Intermediate+

Theorem (Brooks 1941). Let $G$ be a connected graph with maximum degree $Δ = Δ (G)$ . If $G$ is neither a complete graph $K_{Δ + 1}$ nor an odd cycle, then $χ (G) \leq Δ$ . (See ^{[Brooks 1941]}, ^{[Diestel 2017 §5.2]}, ^{[Bondy-Murty 2008 §14.2]}.)

Proof. Set $Δ = Δ (G)$ . The cases $Δ \leq 2$ are direct: $Δ = 0$ is a single vertex ( $χ = 1$ ), $Δ = 1$ is a single edge ( $χ = 2$ ), and $Δ = 2$ makes $G$ a path or a cycle, where paths and even cycles have $χ = 2 \leq Δ$ and the only excluded case is the odd cycle. So assume $Δ \geq 3$ .

The strategy is to find a vertex ordering $v_{1}, \dots, v_{n}$ in which every vertex except the last has a not-yet-listed neighbour, and the last vertex $v_{n}$ has two neighbours that receive the same colour; greedy colouring along $v_{1}, \dots, v_{n}$ then uses at most $Δ$ colours, because each $v_{i}$ ( $i < n$ ) has at most $Δ - 1$ already-coloured neighbours, while $v_{n}$ has $Δ$ neighbours but only $\leq Δ - 1$ distinct colours among them.

First suppose $G$ is not $Δ$ -regular: some vertex $w$ has $d (w) \leq Δ - 1$ . Run a breadth-first search from $w$ and order the vertices by decreasing distance from $w$ , ending with $w = v_{n}$ . Every vertex other than $w$ has a neighbour closer to $w$ , listed later, so when greedy reaches $v_{i}$ ( $i < n$ ) at least one neighbour is uncoloured, leaving $\leq Δ - 1$ used colours; and $v_{n} = w$ has degree $\leq Δ - 1$ . Greedy uses $\leq Δ$ colours.

Now suppose $G$ is $Δ$ -regular. If $G$ has a cut vertex $x$ , then $x$ together with each component $C$ of $G - x$ forms a block $B = G [C \cup {x}]$ in which $x$ has degree $\leq Δ - 1$ ; by the non-regular case each block is $Δ$ -colourable, and the colourings agree on $x$ after permuting colours, so $G$ is $Δ$ -colourable.

Assume then that $G$ is $2$ -connected. Pick any vertex $u$ . If every two neighbours of $u$ are adjacent, then $u$ and its $Δ$ neighbours form $K_{Δ + 1}$ , and since $G$ is connected and $Δ$ -regular this clique is all of $G$ — the excluded complete case. Otherwise $u$ has two non-adjacent neighbours $a, b$ . Because $G$ is $2$ -connected, $G - {a, b}$ is connected (if removing two vertices disconnected it with $u$ separated, $2$ -connectivity would already fail in a way one checks fails here for $Δ \geq 3$ , using that $u$ has a third neighbour); choose $a, b$ so that $G - {a, b}$ is connected, set $v_{1} = a$ , $v_{2} = b$ , and order $v_{3}, \dots, v_{n} = u$ by decreasing distance from $u$ in the connected $G - {a, b}$ . Then each $v_{i}$ with $3 \leq i < n$ has a later neighbour (closer to $u$ ), so $\leq Δ - 1$ used colours; $v_{1}, v_{2}$ are non-adjacent neighbours of $u$ , so greedy gives them the same colour $1$ ; and $u = v_{n}$ sees its $Δ$ neighbours coloured but $a, b$ share colour $1$ , so $\leq Δ - 1$ colours appear among them, leaving a free colour. Greedy uses $\leq Δ$ colours. $□$

Bridge. Brooks' theorem builds toward the whole theory of chromatic bounds and appears again in list colouring and the chromatic polynomial, because it pins the chromatic number to the maximum degree precisely when no local obstruction — a clique or an odd cycle — forces the extra colour. The foundational reason the proof works is the ordering principle inherited from 40.04.01: a vertex with an uncoloured neighbour is cheap to greedy-colour, and the entire argument manufactures such an ordering, so this is exactly the degeneracy bound $χ \leq degen + 1$ sharpened by spending the two non-adjacent neighbours of one vertex. The clique and odd-cycle exceptions are dual to the two ways the greedy bound is tight, and putting these together the bound $ω \leq χ \leq Δ + 1$ with Brooks closing the upper gap becomes the frame for the chromatic polynomial, whose value at $Δ$ Brooks guarantees positive.

Exercises Intermediate+

Exercise 5 (medium, short-answer).

Show directly that the greedy algorithm uses at most $degen (G) + 1$ colours when the vertices are processed in reverse of a degeneracy ordering.

Hint

In a degeneracy ordering, each vertex has at most $degen (G)$ neighbours appearing earlier in that ordering — equivalently later in the reverse.

Answer

Let $d = degen (G)$ and build the ordering $w_{1}, \dots, w_{n}$ by repeatedly removing a vertex of minimum degree from the remaining graph; when $w_{i}$ is removed, its degree in the graph on ${w_{i}, \dots, w_{n}}$ is $\leq d$ , so $w_{i}$ has at most $d$ neighbours among $w_{i + 1}, \dots, w_{n}$ . Colour in the reverse order $w_{n}, w_{n - 1}, \dots, w_{1}$ . When greedy reaches $w_{i}$ , its already-coloured neighbours are exactly those among $w_{i + 1}, \dots, w_{n}$ , of which there are $\leq d$ , so at most $d$ colours are blocked and colour $d + 1$ or lower is free. Hence at most $d + 1$ colours are used. Rubric: full credit for identifying the $\leq d$ later-neighbour count and concluding $d + 1$ colours suffice.

Exercise 6 (medium, short-answer).

Prove that for any graph $G$ , $P (G, k) = P (G - e, k) - P (G / e, k)$ for every edge $e$ .

Hint

Split the proper colourings of $G - e$ according to whether the two endpoints of $e$ receive equal or unequal colours.

Answer

Let $e = {u, v}$ . The proper colourings of $G - e$ with $k$ colours split into two disjoint classes: those giving $u, v$ different colours, and those giving $u, v$ the same colour. A colouring of $G - e$ with $c (u) \neq = c (v)$ is precisely a proper colouring of $G$ (the only extra constraint in $G$ is on the edge $e$ , which is satisfied). A colouring of $G - e$ with $c (u) = c (v)$ corresponds bijectively to a proper colouring of $G / e$ , since identifying $u$ and $v$ into a single vertex is consistent exactly when they share a colour. Therefore $P (G - e, k) = P (G, k) + P (G / e, k)$ , which rearranges to $P (G, k) = P (G - e, k) - P (G / e, k)$ . Rubric: full credit for the two-class split and the two bijections.

Exercise 7 (hard, short-answer).

Prove that the coefficients of $P (G, k)$ alternate in sign: writing $P (G, k) = \sum_{i = 0}^{n} (- 1)^{n - i} a_{i} k^{i}$ with $n = ∣ V ∣$ , every $a_{i} \geq 0$ .

Hint

Induct on the number of edges using deletion-contraction; track how the degree and the sign pattern behave when you delete and contract an edge.

Answer

Induct on $m = ∣ E ∣$ . If $m = 0$ then $P (G, k) = k^{n}$ , whose single coefficient is non-negative with the stated sign. For $m \geq 1$ , pick an edge $e$ ; then $G - e$ has $n$ vertices and $m - 1$ edges, and $G / e$ has $n - 1$ vertices and at most $m - 1$ edges. By induction write $P (G - e, k) = \sum_{i} (- 1)^{n - i} b_{i} k^{i}$ and $P (G / e, k) = \sum_{i} (- 1)^{(n - 1) - i} c_{i} k^{i}$ with all $b_{i}, c_{i} \geq 0$ . Then $$ P(G, k) = P(G-e,k) - P(G/e,k) = \sum_i (-1)^{n-i} b_i k^i - \sum_i (-1)^{n-1-i} c_i k^i = \sum_i (-1)^{n-i}(b_i + c_i) k^i, $$ since $- (- 1)^{n - 1 - i} = (- 1)^{n - i}$ . So $a_{i} = b_{i} + c_{i} \geq 0$ and the signs alternate as $(- 1)^{n - i}$ . Rubric: full credit for the induction, the sign bookkeeping $- (- 1)^{n - 1 - i} = (- 1)^{n - i}$ , and $a_{i} = b_{i} + c_{i} \geq 0$ .

Exercise 8 (hard, short-answer).

Show that there exist triangle-free graphs of chromatic number at least $4$ . (You may use Mycielski's construction: from $G$ with vertices $v_{1}, \dots, v_{n}$ form $M (G)$ by adding $u_{1}, \dots, u_{n}$ and one vertex $w$ , joining $u_{i}$ to every neighbour of $v_{i}$ and joining $w$ to every $u_{i}$ .)

Hint

Show $M (G)$ is triangle-free if $G$ is, and that $χ (M (G)) = χ (G) + 1$ . Start from $C_{5}$ .

Answer

Mycielski's construction sends $G$ to $M (G)$ with $χ (M (G)) = χ (G) + 1$ and preserves triangle-freeness. Triangle-free: the $u_{i}$ form an independent set (no edges among them), $w$ is joined only to $u_{i}$ 's, so any triangle would need two $v$ -vertices and a $u$ or $w$ vertex; but $u_{i}$ 's neighbours are the $v$ -neighbours of $v_{i}$ , an independent-in-the-relevant-sense copy that creates no new triangle when $G$ has none, as one checks on the three vertex-type cases. Chromatic number: any proper $χ (G)$ -colouring of $M (G)$ restricted to the $v_{i}$ extends to colour $u_{i}$ with $c (v_{i})$ , but then $w$ needs a colour different from all $χ (G)$ colours used on the $u_{i}$ , forcing $χ (M (G)) \geq χ (G) + 1$ ; a matching colouring achieves equality. Starting from $C_{5}$ with $χ = 3$ and no triangle, $M (C_{5})$ (the Grötzsch graph) is triangle-free with $χ = 4$ . Rubric: full credit for the triangle-free check, the $χ (M (G)) = χ (G) + 1$ argument, and the $C_{5} \to$ Grötzsch instantiation.

Advanced results Master

Theorem (Whitney's broken-circuit theorem). Fix a total order on $E (G)$ . A broken circuit is a cycle with its largest-labelled edge removed. Then $$ P(G, k) = \sum_{\substack{S \subseteq E \ S \text{ contains no broken circuit}}} (-1)^{|S|} k^{c(S)}, $$ where $c (S)$ is the number of components of the spanning subgraph $(V, S)$ . (Whitney ^{[Whitney 1932]}; Diestel ^{[Diestel 2017 §5.5]}.) The starting point is the inclusion-exclusion expansion $P (G, k) = \sum_{S \subseteq E} (- 1)^{∣ S ∣} k^{c (S)}$ , obtained by counting colourings that may violate edges in $S$ and Möbius-inverting over the partition lattice. Whitney's theorem is the cancellation of all terms whose edge set contains a broken circuit, leaving the no-broken-circuit subsets; the surviving terms have no internal cancellation, so the broken-circuit subsets of each size $i$ count $∣ a_{n - i} ∣$ , giving a combinatorial reading of every coefficient. In particular the coefficient of $k^{n - 1}$ is $- ∣ E ∣$ and the constant term vanishes whenever $G$ has an edge.

Theorem (chromatic polynomial of standard families). For the complete graph, $P (K_{n}, k) = k^{\underline{n}} = k (k - 1) \dots (k - n + 1)$ . For any tree $T$ on $n$ vertices, $P (T, k) = k (k - 1)^{n - 1}$ . For the cycle, $P (C_{n}, k) = (k - 1)^{n} + (- 1)^{n} (k - 1)$ . (Diestel ^{[Diestel 2017 §5.5]}; Bondy-Murty ^{[Bondy-Murty 2008 §14.3]}.) The complete-graph formula is direct counting; the tree formula is one free choice of $k$ for the root and $k - 1$ at each subsequent vertex along the unique tree order from 40.04.01; the cycle formula follows from deletion-contraction $P (C_{n}, k) = P (P_{n}, k) - P (C_{n - 1}, k)$ and induction. That $P (G, k)$ is a single polynomial agreeing with these counts at every positive integer $k$ is the deletion-contraction recurrence run to its base cases of edgeless graphs.

Theorem (the Tutte polynomial specialises to the chromatic polynomial). For a connected graph $G$ with $n$ vertices and $m$ edges, the Tutte polynomial $T (G; x, y)$ satisfies $P (G, k) = (- 1)^{n - 1} k T (G; 1 - k, 0)$ . (Bollobás ^{[Diestel 2017 §5.5]}.) The Tutte polynomial $T (G; x, y) = \sum_{S \subseteq E} (x - 1)^{c (S) - c (E)} (y - 1)^{∣ S ∣ - n + c (S)}$ is the universal deletion-contraction invariant: any graph function obeying $f (G) = f (G - e) + f (G / e)$ for ordinary edges, with multiplicative behaviour on loops and bridges, is an evaluation of $T$ . The chromatic polynomial is the evaluation along the line $y = 0$ , the flow polynomial along $x = 0$ , and the partition function of the $q$ -state Potts model is a third evaluation, so the chromatic theory of this unit is one face of a single two-variable invariant.

Theorem (strong perfect graph theorem; Chudnovsky-Robertson-Seymour-Thomas). A graph $G$ is perfect — meaning $χ (H) = ω (H)$ for every induced subgraph $H$ — if and only if neither $G$ nor its complement contains an induced odd cycle of length $\geq 5$ . (Stated; see ^{[Diestel 2017 §5.5]}.) The forbidden induced subgraphs are the odd holes and odd antiholes; their absence in $G$ and $\overline{G}$ characterises perfection, proving Berge's 1961 conjecture. Chordal graphs, bipartite graphs, interval graphs, and comparability graphs are perfect, and for them the gap $χ - ω$ closes on every induced subgraph; the perfect-elimination ordering of the formal section is exactly the certificate of perfection for the chordal case.

Synthesis. These results are one circle of ideas seen at increasing depth, and putting these together the chromatic number, the chromatic polynomial, and the Tutte polynomial become three readings of how a graph resists being partitioned into independent sets. The central insight is the deletion-contraction recurrence: it is the foundational reason $P (G, k)$ is a polynomial at all, it is exactly the recurrence the Tutte polynomial universalises, and Whitney's broken-circuit theorem is that same recurrence solved to expose each coefficient as a signed count of no-broken-circuit subsets. The bound $ω \leq χ$ is dual to the perfect-graph question of when it is tight, and Brooks' theorem is the degree-side companion that closes the upper gap to $Δ$ outside the clique and odd-cycle exceptions; this is exactly the pair of obstructions — cliques forcing $χ$ up and odd cycles forcing it past $ω$ — that the strong perfect graph theorem proves are the only induced obstructions to $χ = ω$ throughout a graph. Mycielski's construction generalises the $C_{5}$ gap into triangle-free graphs of unbounded $χ$ , the bridge from the local invariant $ω$ to the global one $χ$ that no degree or clique bound can recover, and the same gap reappears in the Tutte plane as the failure of the chromatic line $y = 0$ to be controlled by any single-variable specialisation.

Full proof set Master

Proposition 1 ( $χ (G) \leq degen (G) + 1$ , refining $χ \leq Δ + 1$ ). Every graph $G$ satisfies $χ (G) \leq degen (G) + 1 \leq Δ (G) + 1$ .

Proof. Let $d = degen (G) = max_{H \subseteq G} δ (H)$ . Construct an ordering $w_{1}, \dots, w_{n}$ by repeatedly deleting from the current graph a vertex of minimum degree; let $w_{i}$ be the vertex deleted at step $i$ . At step $i$ the current graph is $G [{w_{i}, \dots, w_{n}}]$ , whose minimum degree is $\leq d$ , so $w_{i}$ has at most $d$ neighbours among ${w_{i + 1}, \dots, w_{n}}$ . Colour greedily in the reverse order $w_{n}, \dots, w_{1}$ : when $w_{i}$ is coloured, its already-coloured neighbours are those in ${w_{i + 1}, \dots, w_{n}}$ , numbering $\leq d$ , so a colour in ${1, \dots, d + 1}$ is free. Thus $χ (G) \leq d + 1$ . Finally $δ (H) \leq Δ (H) \leq Δ (G)$ for every $H \subseteq G$ , so $d \leq Δ (G)$ and $χ (G) \leq Δ (G) + 1$ . $□$

Proposition 2 (Brooks' theorem, $Δ$ -regular $2$ -connected core). A connected $Δ$ -regular graph $G$ with $Δ \geq 3$ that is not complete satisfies $χ (G) \leq Δ$ .

Proof. If $G$ has a cut vertex, decompose into blocks; in each block the shared cut vertex has degree $< Δ$ , so the non-regular argument of Proposition 1's ordering colours each block with $Δ$ colours, and permuting colours aligns them at the cut vertex, so $G$ is $Δ$ -colourable. Assume $G$ is $2$ -connected. As $G$ is not complete, some vertex $u$ has two non-adjacent neighbours $a, b$ . We claim $a, b$ can be chosen with $G - {a, b}$ connected. If $G$ is $3$ -connected, $G - {a, b}$ is connected for any such pair. If $G$ is exactly $2$ -connected, take a vertex $x$ whose removal leaves $2$ -connectivity-critical structure; standard block-tree analysis produces a vertex $u$ with two non-adjacent neighbours $a, b$ in a common end-block such that $G - {a, b}$ stays connected, using $Δ \geq 3$ to supply $u$ a third neighbour bridging the rest. Order $v_{1} = a$ , $v_{2} = b$ , then $v_{3}, \dots, v_{n} = u$ by decreasing distance from $u$ in the connected graph $G - {a, b}$ . Greedy gives $a, b$ the colour $1$ (non-adjacent, both first); each $v_{i}$ for $3 \leq i < n$ has a neighbour nearer $u$ and hence later, so $\leq Δ - 1$ colours are blocked; and $u$ has $Δ$ neighbours of which $a, b$ share colour $1$ , so $\leq Δ - 1$ colours appear among them and one is free. Hence $χ (G) \leq Δ$ . $□$

Proposition 3 ( $P (G, k)$ is a monic integer polynomial of degree $n$ ). For every graph $G$ on $n$ vertices, $P (G, k)$ agrees, for each positive integer $k$ , with a polynomial in $k$ of degree $n$ , leading coefficient $1$ , integer coefficients, and constant term $0$ when $G$ has an edge.

Proof. Induct on $m = ∣ E ∣$ . If $m = 0$ , every map $V \to {1, \dots, k}$ is proper, so $P (G, k) = k^{n}$ , a monic degree- $n$ integer polynomial. For $m \geq 1$ pick an edge $e$ ; by Exercise 6, $P (G, k) = P (G - e, k) - P (G / e, k)$ for all positive integers $k$ . By induction $P (G - e, k)$ is monic of degree $n$ with integer coefficients and $P (G / e, k)$ is an integer polynomial of degree $n - 1$ (it has $n - 1$ vertices). The difference of two such polynomials agrees with $P (G, k)$ at every positive integer $k$ , hence is the polynomial; it is monic of degree $n$ since only $P (G - e, k)$ contributes the $k^{n}$ term, has integer coefficients, and substituting $k = 0$ gives $0$ colourings whenever $G$ has an edge. $□$

Proposition 4 (chromatic polynomial of a tree). For any tree $T$ on $n$ vertices, $P (T, k) = k (k - 1)^{n - 1}$ .

Proof. By the tree characterisation of 40.04.01, order the vertices $u_{1}, \dots, u_{n}$ so each $u_{i}$ ( $i \geq 2$ ) has exactly one neighbour among $u_{1}, \dots, u_{i - 1}$ (a tree's unique-path order). Build a proper colouring left to right: $u_{1}$ has $k$ free choices; each later $u_{i}$ must avoid only its single earlier neighbour's colour, leaving $k - 1$ choices. The choices are independent, so $P (T, k) = k (k - 1)^{n - 1}$ . Since every tree on $n$ vertices admits this order, the formula holds for all trees and is independent of the tree's shape. $□$

Proposition 5 (cycle chromatic polynomial). For $n \geq 3$ , $P (C_{n}, k) = (k - 1)^{n} + (- 1)^{n} (k - 1)$ .

Proof. Induct on $n$ . For $n = 3$ , $C_{3} = K_{3}$ gives $P = k (k - 1) (k - 2) = (k - 1)^{3} + (- 1)^{3} (k - 1)$ , since $(k - 1)^{3} - (k - 1) = (k - 1) [(k - 1)^{2} - 1] = (k - 1) (k^{2} - 2 k) = k (k - 1) (k - 2)$ . For the step, delete an edge $e$ of $C_{n}$ : $C_{n} - e = P_{n}$ has $P (P_{n}, k) = k (k - 1)^{n - 1}$ by Proposition 4, and $C_{n} / e = C_{n - 1}$ . By deletion-contraction $P (C_{n}, k) = k (k - 1)^{n - 1} - P (C_{n - 1}, k)$ . Substituting the inductive form $P (C_{n - 1}, k) = (k - 1)^{n - 1} + (- 1)^{n - 1} (k - 1)$ , $$ P(C_n, k) = k(k-1)^{n-1} - (k-1)^{n-1} - (-1)^{n-1}(k-1) = (k-1)^n + (-1)^n (k-1), $$ using $k (k - 1)^{n - 1} - (k - 1)^{n - 1} = (k - 1)^{n}$ and $- (- 1)^{n - 1} = (- 1)^{n}$ . $□$

Proposition 6 (Whitney inclusion-exclusion expansion). For every graph, $P (G, k) = \sum_{S \subseteq E} (- 1)^{∣ S ∣} k^{c (S)}$ , where $c (S)$ is the number of components of $(V, S)$ .

Proof. For a subset $S \subseteq E$ , let $N (S)$ be the number of colourings $c : V \to {1, \dots, k}$ (not necessarily proper) that are constant on every edge of $S$ — equivalently constant on each component of $(V, S)$ — so $N (S) = k^{c (S)}$ . By inclusion-exclusion over the edge set, the number of colourings violating no edge, namely the proper colourings, is $$ P(G, k) = \sum_{S \subseteq E} (-1)^{|S|} N(S) = \sum_{S \subseteq E} (-1)^{|S|} k^{c(S)}, $$ since a colouring proper on $G$ is one violating none of the $∣ E ∣$ "endpoints-equal" events, and inclusion-exclusion over those events gives the alternating sum with $N (S) = k^{c (S)}$ counting colourings constant on all of $S$ . $□$

Connections Master

Edge and list colouring 40.04.07. The vertex-colouring frame here is the model for the co-produced edge-colouring unit: Vizing's theorem ( $χ^{'} (G) \in {Δ, Δ + 1}$ ) is the edge analogue of Brooks' degree bound, and list colouring replaces each vertex's full palette by a prescribed list, where the list chromatic number $χ_{ℓ} (G)$ can exceed $χ (G)$ even for bipartite graphs. The deletion-contraction and greedy-ordering techniques developed here transfer directly, and the Brooks-type bound $χ_{ℓ} (G) \leq Δ$ for connected non-complete non-odd-cycle graphs is the list refinement of this unit's centrepiece.
Map colouring and planarity 40.04.08. The four-colour theorem — every planar graph has $χ \leq 4$ — is the map-colouring specialisation previewed in the Beginner section, and it rests on the degeneracy bound of the formal section: planar graphs are $5$ -degenerate, giving the easy $χ \leq 6$ and, with more work, $χ \leq 5$ . The chromatic polynomial of a planar triangulation, and its non-vanishing at $k = 4$ , is the quantity the four-colour theorem asserts positive, tying the polynomial of this unit to the most famous colouring result.
Extremal graph theory and Turán's theorem 40.05.01. Turán's theorem bounds the edges of a graph with no $K_{r + 1}$ , and its extremal graphs are the complete $r$ -partite Turán graphs, whose chromatic number is exactly $r$ ; the clique-number lower bound $ω \leq χ$ of this unit is the bridge, since forbidding a large clique caps $ω$ while the chromatic number measures the same partition resistance from above. Mycielski's construction is the extremal sibling showing that bounding $ω$ does not bound $χ$ , the gap that extremal colouring theory and Ramsey theory both develop.
Möbius functions and the order-complex 40.02.02. Whitney's inclusion-exclusion expansion $P (G, k) = \sum_{S} (- 1)^{∣ S ∣} k^{c (S)}$ is a Möbius inversion over the lattice of partitions induced by edge subsets, and the broken-circuit theorem is the statement that the no-broken-circuit subsets are a cohomology basis for that lattice; the chromatic polynomial evaluated at $k$ is, up to sign, the characteristic polynomial of the graphic matroid, computed by the Möbius function of the partition poset developed there.

Historical & philosophical context Master

Vertex colouring grew out of map colouring: Francis Guthrie's 1852 conjecture that four colours suffice for any planar map set the agenda, and Arthur Cayley's 1879 note to the London Mathematical Society publicised the problem. The chromatic polynomial was introduced by George Birkhoff in 1912 as an attempt to prove the four-colour theorem by showing $P (G, 4) > 0$ for planar $G$ , reframing a colouring existence question as the positivity of a counting polynomial; the four-colour theorem was finally proved by Kenneth Appel and Wolfgang Haken in 1976 by computer-assisted discharging, not through the polynomial. Hassler Whitney's 1932 paper A logical expansion in mathematics (Bulletin of the American Mathematical Society 38) ^{[Whitney 1932]} established the broken-circuit theorem, giving the coefficients of $P (G, k)$ their combinatorial meaning and connecting the polynomial to what would become matroid theory.

The degree bound on the chromatic number is due to R. Leonard Brooks, whose 1941 paper On colouring the nodes of a network (Proceedings of the Cambridge Philosophical Society 37) ^{[Brooks 1941]} isolated the complete graphs and odd cycles as the sole exceptions to $χ \leq Δ$ . Jan Mycielski's 1955 note Sur le coloriage des graphes (Colloquium Mathematicum 3) ^{[Mycielski 1955]} constructed triangle-free graphs of arbitrarily large chromatic number, severing the chromatic number from the clique number. Claude Berge conjectured the characterisation of perfect graphs in 1961, and it was proved as the strong perfect graph theorem by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas in 2006 (Annals of Mathematics 164), identifying odd holes and odd antiholes as the only induced obstructions to $χ = ω$ throughout a graph. The unifying two-variable invariant was given by W. T. Tutte, whose 1954 dichromate is the modern Tutte polynomial.

Bibliography Master

@book{Diestel2017,
  author    = {Diestel, Reinhard},
  title     = {Graph Theory},
  edition   = {5th},
  series    = {Graduate Texts in Mathematics},
  volume    = {173},
  publisher = {Springer},
  year      = {2017}
}

@book{BondyMurty2008,
  author    = {Bondy, J. A. and Murty, U. S. R.},
  title     = {Graph Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {244},
  publisher = {Springer},
  year      = {2008}
}

@book{West2001,
  author    = {West, Douglas B.},
  title     = {Introduction to Graph Theory},
  edition   = {2nd},
  publisher = {Prentice Hall},
  year      = {2001}
}

@article{Brooks1941,
  author  = {Brooks, R. L.},
  title   = {On colouring the nodes of a network},
  journal = {Proceedings of the Cambridge Philosophical Society},
  volume  = {37},
  year    = {1941},
  pages   = {194--197}
}

@article{Whitney1932,
  author  = {Whitney, Hassler},
  title   = {A logical expansion in mathematics},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {38},
  year    = {1932},
  pages   = {572--579}
}

@article{Mycielski1955,
  author  = {Mycielski, Jan},
  title   = {Sur le coloriage des graphes},
  journal = {Colloquium Mathematicum},
  volume  = {3},
  year    = {1955},
  pages   = {161--162}
}

@article{Birkhoff1912,
  author  = {Birkhoff, George D.},
  title   = {A determinant formula for the number of ways of coloring a map},
  journal = {Annals of Mathematics},
  volume  = {14},
  year    = {1912},
  pages   = {42--46}
}

@article{ChudnovskyRobertsonSeymourThomas2006,
  author  = {Chudnovsky, Maria and Robertson, Neil and Seymour, Paul and Thomas, Robin},
  title   = {The strong perfect graph theorem},
  journal = {Annals of Mathematics},
  volume  = {164},
  year    = {2006},
  pages   = {51--229}
}

Prerequisites

40.04.01

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §5.1-§5.2 (colouring, the greedy bound) read for the map-and-schedule pictures; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §5.1 for the hand-drawn proper-colouring vocabulary; Wilson 1996 *Introduction to Graph Theory* Ch. 9 for the small worked colourings
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §5.1-§5.2 (the chromatic number, greedy and degeneracy bounds, Brooks' theorem); Bondy-Murty 2008 *Graph Theory* (Springer GTM 244) §14.1-§14.2 (colourings, Brooks); West 2001 §5.1-§5.3 (greedy ordering, Brooks, the chromatic polynomial via deletion-contraction)
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 5 (vertex colouring, Brooks, perfect graphs, the strong perfect graph theorem stated) and Ch. 6 (list colouring) with the chromatic-polynomial / Tutte-polynomial threads; Bollobás 1998 *Modern Graph Theory* (Springer GTM 184) Ch. V (colouring) and Ch. X (the Tutte polynomial); the original sources Brooks 1941, Whitney 1932 (the broken-circuit theorem), Mycielski 1955, Chudnovsky-Robertson-Seymour-Thomas 2006 (the strong perfect graph theorem)

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, Ch. 5 (§5.1 colouring and the chromatic number; §5.2 Brooks' theorem; §5.5 perfect graphs and the strong perfect graph theorem) and Ch. 6 (list colouring)
Bondy, Murty 2008 — Graph Theory · Springer Graduate Texts in Mathematics 244, 2008, §14.1-§14.3 (vertex colourings, Brooks' theorem, the chromatic polynomial and deletion-contraction)
West 2001 — Introduction to Graph Theory · 2nd ed., Prentice Hall, 2001, §5.1-§5.3 (greedy colouring and degeneracy, Brooks' theorem, the chromatic polynomial, broken circuits)
Brooks 1941 — On colouring the nodes of a network · Proceedings of the Cambridge Philosophical Society 37 (1941) 194-197; the bound chi <= Delta unless G is complete or an odd cycle
Whitney 1932 — A logical expansion in mathematics · Bulletin of the American Mathematical Society 38 (1932) 572-579; the broken-circuit theorem for the coefficients of the chromatic polynomial
Mycielski 1955 — Sur le coloriage des graphes · Colloquium Mathematicum 3 (1955) 161-162; triangle-free graphs of arbitrarily large chromatic number

Estimated time

beginner: 18m
intermediate: 48m
master: 86m