Proof of the Heawood Bound

The Bound and Its Scope

The Heawood bound limits the number of colors needed for a graph embedded on a surface. Its numerical value depends on the surface’s Euler characteristic. The central proof uses two ingredients: an upper bound on the number of edges in an embedded simple graph, and the fact that a minimal graph that cannot be colored with a fixed number of colors must have sufficiently large minimum degree.

Throughout, a surface means a compact, connected surface without boundary, and graphs are finite and simple. A proper coloring assigns colors to vertices so that adjacent vertices receive different colors. The chromatic number $\chi(G)$ is the least number of colors in a proper coloring of $G$. The Euler characteristic of the surface $S$ is denoted by $\chi(S)$; it is not the graph’s chromatic number.

Definition: For a surface $S$, define its Heawood number by $$ H(S)=\left\lfloor\frac{7+\sqrt{49-24\chi(S)}}{2}\right\rfloor. $$ The Heawood bound is the assertion that every finite simple graph embedded on $S$ satisfies $\chi(G)\le H(S)$.

Because $\chi(S)\le2$, the expression under the square root is nonnegative. The proof below derives the bound from the surface edge bound when $\chi(S)\le0$. The projective plane, with $\chi(S)=1$, and the sphere, with $\chi(S)=2$, are handled by separate coloring theorems.

The Surface Edge Bound

We use the following standard surface edge bound, established in the earlier material on surface edge bounds: if a finite simple graph with $n\ge3$ vertices and $m$ edges is embedded on a surface $S$, then $$ m\le 3n-3\chi(S). $$ The inequality does not require the embedding to be cellular. In this tutorial it will only be applied to a graph with at least three vertices, so no small-order exception is needed.

The other ingredient is a minimal-counterexample argument. If a graph is not colorable with $h$ colors, choose among its subgraphs one that is not $h$-colorable and has the fewest vertices. Every graph obtained from it by deleting a vertex is $h$-colorable. This forces each vertex of the minimal graph to have degree at least $h$: otherwise the coloring after deletion could be extended to the removed vertex.

Theorem (Heawood bound for $\chi(S)\le0$): Let $S$ be a compact, connected surface without boundary with $\chi(S)\le0$. Every finite simple graph $G$ embedded on $S$ satisfies $$ \chi(G)\le \left\lfloor\frac{7+\sqrt{49-24\chi(S)}}{2}\right\rfloor. $$

Proof. Set $h=H(S)$, and suppose, for contradiction, that some finite simple graph embedded on $S$ is not $h$-colorable. Choose a subgraph $G$ that is not $h$-colorable and is minimal in its number of vertices. Write $n=|V(G)|$ and $m=|E(G)|$. Since $h\ge7$, a graph on at most $h$ vertices can be colored with $h$ colors by giving every vertex a different color. Therefore $n\ge h+1\ge8$.

For every vertex $v$ of $G$, the graph $G-v$ is $h$-colorable by minimality. If $\deg(v)\le h-1$, at most $h-1$ colors appear on its neighbors in such a coloring, leaving at least one of the $h$ colors available for $v$. This would color $G$, a contradiction. Thus every vertex has degree at least $h$, and the handshake lemma gives $$ 2m=\sum_{v\in V(G)}\deg(v)\ge hn. $$ The surface edge bound applies because $n\ge8$. Combining the two edge estimates yields $$ hn\le 2m\le 6n-6\chi(S), $$ so $$ (h-6)n\le -6\chi(S). $$ Since $h\ge7$, the factor $h-6$ is positive. Since $n\ge h+1$, it follows that $$ (h-6)(h+1)\le -6\chi(S). $$ Rearranging this inequality gives $$ (h+1)^2-7(h+1)+6\chi(S)\le0. $$

Set $R=(7+\sqrt{49-24\chi(S)})/2$, the positive root of $x^2-7x+6\chi(S)=0$. The other root is $(7-\sqrt{49-24\chi(S)})/2\le0$, while $h\ge7$. By the definition of the floor, $h\le R<h+1$. Consequently $h+1>R$, and the quadratic $x^2-7x+6\chi(S)$, which is positive for $x>R$, satisfies $$ (h+1)^2-7(h+1)+6\chi(S)>0. $$ This contradicts the inequality just obtained. Hence no such minimal counterexample exists, and every graph embedded on $S$ is $h$-colorable. $\square$

Reading the Integer Bound Carefully

The floor in the Heawood number matters. It is not enough to find a real-valued threshold; the contradiction uses that $h$ is the integer part of the positive root. The strict inequality $R<h+1$ makes the quadratic positive at $h+1$, which conflicts with what a hypothetical minimal obstruction would require.

Worked Example: Euler Characteristic Zero

Let $S$ have $\chi(S)=0$, as on the torus. The expression in the bound is $$ \frac{7+\sqrt{49-24(0)}}{2}=\frac{7+7}{2}=7, $$ so $h=7$. The quadratic is $f(x)=x^2-7x$. At the proposed integer bound, $f(7)=49-49=0$; at the next integer, $f(8)=64-56=8>0$. Thus $7$ is the floor of the positive root.

If a minimal graph embedded on $S$ were not 7-colorable, it would have $n\ge8$ vertices and degree at least 7 at every vertex. Hence $2m\ge7n$. The surface edge bound gives $2m\le6n-6(0)=6n$. Together these imply $7n\le6n$, or $n\le0$, contradicting $n\ge8$.

Check: the two edge estimates require $7n\le6n$, which is impossible for $n\ge8$. This agrees with the theorem’s conclusion of at most 7 colors.

Worked Example: Euler Characteristic Negative Two

Let $\chi(S)=-2$. Then $$ \frac{7+\sqrt{49-24(-2)}}{2} =\frac{7+\sqrt{97}}{2}. $$ Since $9^2=81<97<100=10^2$, we have $9<\sqrt{97}<10$, so $8< (7+\sqrt{97})/2<8.5$ and the floor is $h=8$. Equivalently, $f(x)=x^2-7x-12$ has $f(8)=64-56-12=-4$ and $f(9)=81-63-12=6$, confirming that its positive root lies between 8 and 9.

A minimal graph that is not 8-colorable would have $n\ge9$ vertices and $2m\ge8n$. The edge bound gives $2m\le6n-6(-2)=6n+12$. Therefore $8n\le6n+12$, so $2n\le12$ and $n\le6$. This contradicts $n\ge9$.

Check: substituting the resulting upper estimate $n\le6$ into the necessary condition $n\ge9$ gives an immediate contradiction. Hence every such graph is 8-colorable.

Worked Example: Euler Characteristic Negative Four

Let $\chi(S)=-4$. The expression is $$ \frac{7+\sqrt{49-24(-4)}}{2} =\frac{7+\sqrt{145}}{2}. $$ Since $12^2=144<145<169=13^2$, we have $12<\sqrt{145}<13$, and therefore $9.5<(7+\sqrt{145})/2<10$. Its floor is $h=9$. Directly, $f(x)=x^2-7x-24$ has $f(9)=81-63-24=-6$ and $f(10)=100-70-24=6$, placing its positive root between 9 and 10.

A minimal graph that is not 9-colorable would have $n\ge10$ and $2m\ge9n$. The edge bound gives $2m\le6n-6(-4)=6n+24$. Thus $9n\le6n+24$, which implies $3n\le24$ and $n\le8$, contradicting $n\ge10$.

Check: the lower and upper estimates require $9n\le6n+24$; at the minimum permitted order $n=10$, this would read $90\le84$, which is false.

The Exceptional Cases

The same edge-count proof is not the argument supplied here for every surface. For $\chi(S)=1$, the surface is the projective plane and the formula gives $$ \left\lfloor\frac{7+\sqrt{49-24}}{2}\right\rfloor =\left\lfloor\frac{7+5}{2}\right\rfloor=6. $$ The required result is the standard projective-plane six-color theorem: every finite simple graph embedded in the projective plane is 6-colorable. Its proof is a separate coloring theorem, not a consequence claimed here of the nonpositive-Euler-characteristic argument.

For $\chi(S)=2$, the surface is the sphere and the formula gives $$ \left\lfloor\frac{7+\sqrt{49-48}}{2}\right\rfloor =\left\lfloor\frac{7+1}{2}\right\rfloor=4. $$ This case is the Four Color Theorem: every planar graph is 4-colorable. It is a standard result whose proof is not repeated here. The surface edge bound alone does not establish four-colorability.

These separate inputs are essential to the stated scope. In particular, a conclusion of 5-colorability would not establish 4-colorability on the sphere, and a conclusion of 7-colorability would not establish 6-colorability on the projective plane. An upper bound on the number of colors must match the claimed number exactly or be stronger.

Common Pitfalls and Why the Proof Works

Off-by-one coloring error. Suppose an argument assumes that a graph is not $h$-colorable, then rules out that assumption by showing it is $(h+1)$-colorable. That does not prove the desired conclusion: $K_{h+1}$ is $(h+1)$-colorable, but it is not $h$-colorable. The correction is to choose a minimal graph that is not $h$-colorable and use the edge estimates to contradict its existence. In the proof above, the contradiction therefore establishes $h$-colorability itself.

Dropping the floor inequality. The integer $h=\lfloor R\rfloor$ satisfies $h\le R<h+1$, not $h=R$ in general. The contradiction depends on evaluating the quadratic at $h+1$, which is strictly greater than its positive root. Replacing the strict inequality $R<h+1$ by a non-strict one would not justify the required positive sign.

Extending the edge-count argument beyond its stated range. The proof explicitly uses $\chi(S)\le0$ to have $h\ge7$, so that $h-6>0$ and the order bound can be used in the stated direction. The sphere and projective-plane conclusions above rely on their own coloring theorems. Keeping these cases separate prevents an edge-count estimate from being credited with a sharper coloring result than it proves.

The proof illustrates how an embedding constraint becomes a coloring bound. A hypothetical minimal obstruction forces every vertex to have high degree, so it forces many edges. The surface restricts how many edges can be present. When those two counts are incompatible, the obstruction cannot exist. The Heawood formula packages the resulting integer threshold in terms of Euler characteristic.

Check Your Understanding

Use the minimal-counterexample argument and keep the distinction between the proved range and the exceptional cases.

For $\chi(S)=-1$, evaluate the Heawood number and verify it by locating the positive root between consecutive integers.
In a minimal graph that is not $h$-colorable, explain why every vertex has degree at least $h$.
For $\chi(S)=-3$, write the two edge-count inequalities a minimal non-$h$-colorable graph would satisfy.
Why does the proof need $R<h+1$, rather than only $h\le R$, when it evaluates the quadratic?
State which separate coloring theorem supplies the bound when $\chi(S)=1$, and which supplies it when $\chi(S)=2$.

What You'll Learn