Graph Coloring

The chromatic number $\chi(G)$, greedy coloring, Brooks' theorem, the chromatic polynomial, edge coloring and Vizing's theorem, and an overview of the four color theorem.

Folio Official

March 1, 2026

1 Vertex Coloring

Definition 1 (Proper vertex coloring).

A proper vertex coloring of a graph

G = (V, E)

is a map

c : V \to {1, 2, \dots, k}

such that

c (u) \neq = c (v)

whenever

{u, v} \in E

. If such a coloring exists, we say

G

k

-colorable.

Definition 2 (Chromatic number).

The smallest

k

for which

G

k

-colorable is called the chromatic number of

G

and is denoted

χ (G)

Example 3.

χ (K_{n}) = n

(in a complete graph, every pair of vertices is adjacent, so

n

colors are required).

χ (C_{2 k}) = 2

(even cycles are bipartite).

χ (C_{2 k + 1}) = 3

(odd cycles require three colors).

The odd cycle $C_{5}$ cannot be properly colored with two colors, but three colors suffice:

2 Greedy Coloring

Theorem 4 (Greedy upper bound).

For any graph

G

χ (G) \leq Δ (G) + 1

, where

Δ (G)

is the maximum degree of

G

Proof.

Fix an arbitrary ordering

v_{1}, v_{2}, \dots, v_{n}

of the vertices. Color each

v_{i}

with the smallest color not already used by its previously colored neighbors. Since

v_{i}

has at most

Δ (G)

neighbors, at most

Δ (G)

colors are excluded. A valid color can therefore always be found within

{1, 2, \dots, Δ (G) + 1}

. By induction, every vertex receives a valid color using at most

Δ (G) + 1

colors. □

3 Brooks' Theorem

Theorem 5 (Brooks' theorem (1941)).

G

is a connected simple graph that is neither a complete graph nor an odd cycle, then

χ (G) \leq Δ (G)

Proof.

We sketch the main ideas. Assume

Δ = Δ (G) \geq 3

(the cases

Δ \leq 2

are straightforward). If

G

is not

Δ

-regular, there exists a vertex

v

with

de g (v) < Δ

. Placing

v

last in the greedy ordering guarantees that

Δ

colors suffice.

When

G

Δ

-regular but not complete, there exist two non-adjacent vertices

u

and

w

. Assigning

u

and

w

the same color and then applying greedy coloring in a suitable BFS order produces a proper coloring using at most

Δ

colors. □

4 The Chromatic Polynomial

Definition 6 (Chromatic polynomial).

For a graph

G

, let

P (G, k)

denote the number of proper

k

-colorings of

G

. The function

P (G, k)

is a polynomial in

k

, called the chromatic polynomial of

G

Theorem 7 (Deletion–contraction formula).

For any edge

e = {u, v}

G

, let

G - e

denote the graph with

e

deleted and

G / e

the graph with

e

contracted. Then

P (G, k) = P (G - e, k) - P (G / e, k) .

Proof.

Among the proper

k

-colorings of

G - e

, those with

c (u) \neq = c (v)

are also proper colorings of

G

, and those with

c (u) = c (v)

correspond bijectively to proper colorings of

G / e

. Thus

P (G - e, k) = P (G, k) + P (G / e, k)

. □

Example 8.

The chromatic polynomial of the complete graph is

P (K_{n}, k) = k (k - 1) (k - 2) \dots (k - n + 1)

. For a tree

T

n

vertices,

P (T, k) = k (k - 1)^{n - 1}

5 Edge Coloring and Vizing's Theorem

Definition 9 (Edge coloring).

A proper edge coloring of a graph

G

assigns colors to edges so that no two edges sharing an endpoint receive the same color. The minimum number of colors required is the chromatic index, denoted

χ^{'} (G)

Since all edges incident to any vertex must receive distinct colors, $χ^{'} (G) \geq Δ (G)$ is immediate.

Theorem 10 (Vizing's theorem (1964)).

For every simple graph

G

Δ (G) \leq χ^{'} (G) \leq Δ (G) + 1.

Remark 11.

Vizing's theorem partitions simple graphs into two classes: Class 1 graphs with

χ^{'} (G) = Δ (G)

and Class 2 graphs with

χ^{'} (G) = Δ (G) + 1

. It is known that every bipartite graph is Class 1 (a consequence of Kö

6 The Four Color Theorem

Theorem 12 (Four color theorem (Appel–Haken, 1976)).

Every planar graph is

4

-colorable. That is,

χ (G) \leq 4

for every planar graph

G

Remark 13.

The four color theorem was the first major theorem to be proved with essential assistance from a computer. The proof uses the notions of an unavoidable set and reducibility, and involves computer verification of roughly

1500

configurations. In 1997, Robertson, Sanders, Seymour, and Thomas gave a simplified proof, and in 2005, Gonthier and Werner produced a formal verification using the Coq proof assistant.

The weaker statement

χ (G) \leq 5

(the five color theorem) admits an elementary proof via Kempe chains: by

E \leq 3 V - 6

, a vertex

v

of degree at most

5

exists. Remove

v

, color the rest inductively with five colors, and restore

v

. If the at most five neighbors of

v

use all five colors, a Kempe chain argument frees one color for

v

Graph Theory Discrete Mathematics Textbook Graph Coloring Chromatic Polynomial Four Color Theorem

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Graph Coloring

The chromatic number $\chi(G)$, greedy coloring, Brooks' theorem, the chromatic polynomial, edge coloring and Vizing's theorem, and an overview of the four color theorem.

Folio Official

March 1, 2026

1 Vertex Coloring

Definition 1 (Proper vertex coloring).

A proper vertex coloring of a graph

G = (V, E)

is a map

c : V \to {1, 2, \dots, k}

such that

c (u) \neq = c (v)

whenever

{u, v} \in E

. If such a coloring exists, we say

G

k

-colorable.

Definition 2 (Chromatic number).

The smallest

k

for which

G

k

-colorable is called the chromatic number of

G

and is denoted

χ (G)

Example 3.

χ (K_{n}) = n

(in a complete graph, every pair of vertices is adjacent, so

n

colors are required).

χ (C_{2 k}) = 2

(even cycles are bipartite).

χ (C_{2 k + 1}) = 3

(odd cycles require three colors).

The odd cycle $C_{5}$ cannot be properly colored with two colors, but three colors suffice:

2 Greedy Coloring

Theorem 4 (Greedy upper bound).

For any graph

G

χ (G) \leq Δ (G) + 1

, where

Δ (G)

is the maximum degree of

G

Proof.

Fix an arbitrary ordering

v_{1}, v_{2}, \dots, v_{n}

of the vertices. Color each

v_{i}

with the smallest color not already used by its previously colored neighbors. Since

v_{i}

has at most

Δ (G)

neighbors, at most

Δ (G)

colors are excluded. A valid color can therefore always be found within

{1, 2, \dots, Δ (G) + 1}

. By induction, every vertex receives a valid color using at most

Δ (G) + 1

colors. □

3 Brooks' Theorem

Theorem 5 (Brooks' theorem (1941)).

G

is a connected simple graph that is neither a complete graph nor an odd cycle, then

χ (G) \leq Δ (G)

Proof.

We sketch the main ideas. Assume

Δ = Δ (G) \geq 3

(the cases

Δ \leq 2

are straightforward). If

G

is not

Δ

-regular, there exists a vertex

v

with

de g (v) < Δ

. Placing

v

last in the greedy ordering guarantees that

Δ

colors suffice.

When

G

Δ

-regular but not complete, there exist two non-adjacent vertices

u

and

w

. Assigning

u

and

w

the same color and then applying greedy coloring in a suitable BFS order produces a proper coloring using at most

Δ

colors. □

4 The Chromatic Polynomial

Definition 6 (Chromatic polynomial).

For a graph

G

, let

P (G, k)

denote the number of proper

k

-colorings of

G

. The function

P (G, k)

is a polynomial in

k

, called the chromatic polynomial of

G

Theorem 7 (Deletion–contraction formula).

For any edge

e = {u, v}

G

, let

G - e

denote the graph with

e

deleted and

G / e

the graph with

e

contracted. Then

P (G, k) = P (G - e, k) - P (G / e, k) .

Proof.

Among the proper

k

-colorings of

G - e

, those with

c (u) \neq = c (v)

are also proper colorings of

G

, and those with

c (u) = c (v)

correspond bijectively to proper colorings of

G / e

. Thus

P (G - e, k) = P (G, k) + P (G / e, k)

. □

Example 8.

The chromatic polynomial of the complete graph is

P (K_{n}, k) = k (k - 1) (k - 2) \dots (k - n + 1)

. For a tree

T

n

vertices,

P (T, k) = k (k - 1)^{n - 1}

5 Edge Coloring and Vizing's Theorem

Definition 9 (Edge coloring).

A proper edge coloring of a graph

G

assigns colors to edges so that no two edges sharing an endpoint receive the same color. The minimum number of colors required is the chromatic index, denoted

χ^{'} (G)

Since all edges incident to any vertex must receive distinct colors, $χ^{'} (G) \geq Δ (G)$ is immediate.

Theorem 10 (Vizing's theorem (1964)).

For every simple graph

G

Δ (G) \leq χ^{'} (G) \leq Δ (G) + 1.

Remark 11.

Vizing's theorem partitions simple graphs into two classes: Class 1 graphs with

χ^{'} (G) = Δ (G)

and Class 2 graphs with

χ^{'} (G) = Δ (G) + 1

. It is known that every bipartite graph is Class 1 (a consequence of Kö

6 The Four Color Theorem

Theorem 12 (Four color theorem (Appel–Haken, 1976)).

Every planar graph is

4

-colorable. That is,

χ (G) \leq 4

for every planar graph

G

Remark 13.

1500

configurations. In 1997, Robertson, Sanders, Seymour, and Thomas gave a simplified proof, and in 2005, Gonthier and Werner produced a formal verification using the Coq proof assistant.

The weaker statement

χ (G) \leq 5

(the five color theorem) admits an elementary proof via Kempe chains: by

E \leq 3 V - 6

, a vertex

v

of degree at most

5

exists. Remove

v

, color the rest inductively with five colors, and restore

v

. If the at most five neighbors of

v

use all five colors, a Kempe chain argument frees one color for

v

Graph Theory Discrete Mathematics Textbook Graph Coloring Chromatic Polynomial Four Color Theorem

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Graph Coloring

1 Vertex Coloring

2 Greedy Coloring

3 Brooks' Theorem

4 The Chromatic Polynomial

5 Edge Coloring and Vizing's Theorem

6 The Four Color Theorem

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

Graph Coloring

1 Vertex Coloring

2 Greedy Coloring

3 Brooks' Theorem

4 The Chromatic Polynomial

5 Edge Coloring and Vizing's Theorem

6 The Four Color Theorem

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences