From Surface to Color Bound
A surface constrains how complicated a graph can be when drawn on it without crossings. The Heawood bound turns one numerical feature of the surface—its Euler characteristic—into an upper bound on the number of colors needed. Applying the formula is straightforward; interpreting the answer requires care. A bound of seven says that seven colors always suffice. By itself, it does not say that some graph on the surface actually needs seven.
Throughout, a graph is 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 such a coloring. We write \(\chi(\Sigma)\) for the Euler characteristic of a surface \(\Sigma\). These are different quantities: \(\chi(G)\) concerns colors, while \(\chi(\Sigma)\) is a topological invariant.
The expression \(H(\Sigma)\) is an integer upper bound. To establish the actual maximum chromatic number of graphs embeddable on a surface, two things are needed: an upper bound that applies to every such graph, and an example that attains that bound. The second part is a lower-bound argument: if a graph embedded on \(\Sigma\) requires \(k\) colors, then the maximum is at least \(k\).
For the surfaces considered here, the Euler characteristics are \(2\) for the sphere, \(1\) for the projective plane, and \(0\) for both the torus and Klein bottle. The two surfaces with Euler characteristic zero will therefore have the same value in the Heawood formula, even though their actual maximum chromatic numbers differ.
Calculating the Four Bounds
Worked Example: The Sphere
For the sphere \(S^2\), substitute \(\chi(S^2)=2\) into the formula:
Thus every graph that embeds on the sphere is at most four-colorable. The bound is attained: take \(G=K_4\), with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). This graph embeds on the sphere as the edges of a tetrahedron. Every pair of its vertices is adjacent, so all four vertices must receive different colors. Hence \(\chi(G)=4\), and the maximum for the sphere is exactly four.
Check: the edge list contains six edges. Independently, every vertex has degree three, so the degree sum is \(4\cdot3=12\), and the handshake lemma gives \(12/2=6\) edges. This agrees with the list and with the tetrahedron graph.
Worked Example: The Projective Plane
For the projective plane \(\mathbb{RP}^2\), use \(\chi(\mathbb{RP}^2)=1\):
Every graph embeddable on the projective plane is therefore at most six-colorable. This bound is attained by a standard embedding of \(K_6\) on the projective plane. Explicitly, let \(V(G)=\{1,2,3,4,5,6\}\) and \(E(G)=\{ij:1\le i<j\le6\}\). Since every pair of vertices is adjacent, a proper coloring needs six distinct colors, so \(\chi(G)=6\). The standard projective-plane embedding supplies the required example; its construction is not needed for this calculation.
Check: each vertex of \(K_6\) is adjacent to the other five, so the degree sum is \(6\cdot5=30\), giving \(30/2=15\) edges. The edge-set definition also counts one edge for each of the \(6\cdot5/2=15\) unordered pairs. Thus the graph specified is indeed the complete graph on six vertices.
Worked Example: The Torus
The torus \(T^2\) has Euler characteristic \(0\). Substitution gives
So seven colors always suffice for a graph embedded on the torus. The bound is attained by the standard toroidal embedding of \(K_7\). Take \(V(G)=\{1,2,3,4,5,6,7\}\) and \(E(G)=\{ij:1\le i<j\le7\}\). Every two vertices are adjacent, so \(\chi(G)=7\). Consequently, the maximum chromatic number for the torus is exactly seven.
Check: each of the seven vertices has degree six, so the degree sum is \(7\cdot6=42\), and the edge count is \(42/2=21\). Counting unordered vertex pairs independently gives \(7\cdot6/2=21\) as well, consistent with the complete graph specified.
The Klein Bottle: Same Bound, Different Maximum
Worked Example: Applying the Bound to the Klein Bottle
The Klein bottle \(\mathcal K\) also has Euler characteristic \(0\). Its Heawood calculation is therefore
The formula guarantees that seven colors suffice, but it does not show that seven are necessary. In fact, the Klein bottle is an exceptional case: every graph embedded on it is six-colorable, and a standard embedding of \(K_6\) on the Klein bottle shows that six colors are sometimes necessary. Thus the actual maximum is six, not seven. The six-colorability assertion is the standard Klein-bottle coloring result; its proof is beyond this tutorial. The example \(K_6\) gives the matching lower bound, since all its vertices are pairwise adjacent.
Check: for this \(K_6\), the six vertices each have degree five, giving degree sum \(6\cdot5=30\) and edge count \(30/2=15\). Counting its unordered pairs gives \(6\cdot5/2=15\), so the specified complete graph has the required six mutually adjacent vertices.
The torus and Klein bottle make the distinction especially visible. Their Euler characteristics are equal, so the Heawood formula gives the same upper bound for both. But equality in the bound depends on which graphs actually embed on each surface, not just on the arithmetic in the formula. On the torus, \(K_7\) attains the bound. On the Klein bottle, the sharper six-colorability result rules out any seven-chromatic embedded graph.
Bounds, Attainment, and Exact Maxima
For a surface \(\Sigma\), consider the set of chromatic numbers of all finite simple graphs that embed on \(\Sigma\). The Heawood bound says every member of this set is at most \(H(\Sigma)\). If an embedded graph has chromatic number \(H(\Sigma)\), then the largest value in the set is exactly \(H(\Sigma)\): no value is larger, and the example reaches the bound.
That reasoning establishes exact maxima for the sphere, projective plane, and torus. On the sphere, the complete graph \(K_4\) supplies the lower bound of four; the Heawood bound supplies the upper bound of four. On the projective plane, the standard embedding of \(K_6\) supplies six, matching the bound. On the torus, the standard embedding of \(K_7\) supplies seven, again matching the bound. These embedding facts are standard constructions; the color lower bounds follow directly from completeness.
For the Klein bottle, the formula alone supplies only the upper bound of seven. The six-colorability theorem improves that upper bound to six, and the embedded \(K_6\) supplies the lower bound of six. Together, these yield the exact maximum. This is an important logical pattern: an upper bound and an example matching it prove an exact value, but if no example attains the bound, that absence alone does not prove a smaller maximum. A sharper upper bound or a separate argument is required.
| Surface | Euler characteristic | Heawood bound | Actual maximum | Attainment or refinement |
|---|---|---|---|---|
| Sphere | 2 | 4 | 4 | \(K_4\) embeds |
| Projective plane | 1 | 6 | 6 | \(K_6\) embeds |
| Torus | 0 | 7 | 7 | \(K_7\) embeds |
| Klein bottle | 0 | 7 | 6 | Sharper six-colorability result; \(K_6\) embeds |
For the sphere, the four-color theorem is also a standard route to the upper bound of four; it is consistent with the Heawood calculation. The tetrahedral embedding of \(K_4\) shows that this cannot be reduced to three. For the other surfaces in the table, the complete-graph examples make the lower-bound step explicit: in \(K_n\), each of the \(n\) vertices is adjacent to all the others, so no two can share a color.
Common Pitfall: Treating the Bound as an Equality
A frequent error is to report the output of the Heawood formula as the exact maximum without checking whether the bound is attained. For instance, the calculation for the Klein bottle gives seven. The incorrect conclusion is “the Klein bottle’s maximum chromatic number is seven.” That conclusion does not follow from the calculation: it confuses “every graph needs at most seven colors” with “some graph needs seven colors.” The correction uses the standard six-colorability theorem and the embedded \(K_6\): every graph needs at most six, and this particular graph needs six, so the maximum is six.
A second source of mistakes is substituting a genus parameter where the formula requires Euler characteristic. The sphere has Euler characteristic two, not zero. Substituting zero would calculate \(\lfloor(7+\sqrt{49})/2\rfloor=7\), which is not the sphere’s Heawood bound. First identify the surface and its Euler characteristic; then substitute that value and evaluate the square root and floor.
Check Your Understanding
For each question, distinguish what follows from the Heawood bound alone from what requires an example or a sharper result.
- Calculate the Heawood bound for a surface with Euler characteristic \(1\). What surface in this tutorial has that Euler characteristic?
- Why does an embedding of \(K_7\) on the torus, together with the Heawood bound, determine the exact maximum there?
- The torus and Klein bottle both have Euler characteristic \(0\). Why does this give the same Heawood bound but not the same actual maximum?
- What does the Heawood calculation for the Klein bottle establish on its own, and what additional result is needed to conclude that the maximum is six?
- Explain why a complete graph \(K_n\) requires \(n\) colors.