# Heawood's Theorem

How to contact me.

Back to the
Graph
Theory Index.

Before discussing results about graphs embedded on surfaces,
it is useful to define those surfaces.
Our basic surface is the sphere, denoted *S*_{0}.
A graph *G* is embedded on *S*_{0} if
the vertices of *G* are points of *S*_{0},
the edges of *G* are continuous (and smooth) arcs on *S*_{0},
connecting the appropriate pairs of vertices, and
no two edges of *G* have any points in common, except at vertices shared by the edges.

Once a graph has been embedded on the sphere, the sphere is subdivided into regions, called faces, whose boundaries are sets (or sequences) of edges.

Any graph embedded on the sphere can also be considered as embedded in the plane, by the simple expedient of puncturing one face. Of course, one embedding on the sphere may yield many different embeddings on the plane, each arising from puncturing a different face.
A graph which can be embedded in the plane or on the sphere is called *planar*.

We now consider possible modifications (simple surgery) which may be made.
A *crosscap* is a region, usually considered as a circular region,
with the property that edges which enter at some point on the boundary of the crosscap
emerge at the diametrically opposite point on the boundary,
no two edges enter at diametrically opposite points of the crosscap,
and any two edges entering the crosscap do not intersect (see Figure 1).
A single crosscap acts like a möbius strip.
A surface with *c* pairwise disjoint crosscaps is frequently referred to as *N*_{c}.
The *projective plane* is *N*_{1}.
The *Klein bottle* is *N*_{2}.

A *handle* may be considered as a disjoint pair of circular regions *H*_{1} and *H*_{2}.
If the edges entering *H*_{1} are listed cyclically clockwise as
*e*_{1}, *e*_{2}, ..., *e*_{k}, then these emerge at *H*_{2} in the same cyclic ordering, but counterclockwise (see Figure 4).
A surface with *g* pairwise disjoint handles is frequently referred to as *S*_{g}.
The *torus* is
*S*_{1}.

The *Euler characteristic* of *S*_{g} is *2 - 2g*, and the
*Euler characteristic* of *N*_{c} is *2 - c*.

In these notes,
a surface with *g* handles and *c* crosscaps, pairwise disjoint, will be denoted *S*_{g,c}.

**Euler's Theorem and generalization**.
Let *G* be a finite, connected graph embedded on a surface *S*_{g,c} so that every face is a *2*-cell.
Then, *ν - ε + φ = 2 - 2g - c*,
where *ν* is the number of vertices of *G*,
*ε* is the number of edges of *G*, and
*φ* is the number of faces of *G*.

**Proof**. We proceed by induction on the number *g + c*.

While I don't explicit use the following in this proof,
it is nice to note that, we may assume, whenever necessary,
that every face of *G* has degree at most three.
If *F* is a face of degree greater than three, then let *e* be a chord of *F*.
To embed the graph *G+e* on *S*_{g,c},
we start with the embedding of *G* and add the edge *e* in the *2*-cell *F*.
This partitions *F* into two *2*-cells, and does not effect the other faces of *G*.
Also, *G+e* is connected.
The number of faces has increased by one, and the number of edges by one. Thus,
*ν(G) - ε(G) + φ(G) = ν(G+e) - ε(G+e) + φ(G+e)*,
and the result holds for *G* iff it holds for *G+e*.
We define the excess of any face *K* to be *|d(K)-3|*,
where *d(K)* is the degree of *K*,
and we define the excess of (the embedding of) *G* to be the sum of the excesses of the faces.
The excess of *G+e* is less than the excess of *G*,
and we cannot add edges indefinitely.

Suppose that *C* is a crosscap of *S*_{g,c} and that the the edges traversing *C* are
*e*_{1}, *e*_{2}, ..., *e*_{k},
*e*_{1}, *e*_{2}, ..., *e*_{k}, in this cyclic order.
Each edge is listed twice, since it enters and leaves at diametrically opposite points of *C*.
We add vertices *v*_{1}, *v*_{2}, ..., *v*_{2k},
cyclically around (but slightly outside of) *C*, with *v*_{i} and
*v*_{k+i} on *e*_{i} (see Figure 2).
This adds *2k* vertices and *2k* edges to the graph, but does not effect the interior of any face.
Now, add edges *v*_{i}v_{i+1}, subscripts modulo *2k* (see Figure 3).
Each edge that is added lies entirely within a face of the embedding,
and thus subdivides that face into two faces, each of which is a *2*-cell,
increasing the number of faces by one and the number of edges by one.
Each of these operations results in a connected graph.
Let *G'* denote the graph that is obtained after all of these operations. Then,
*ν(G') = ν(G) + 2k*,
*ε(G') = ε(G) + 4k*,
*φ(G') = φ(G) + 2k*,
*ν(G) - ε(G) + φ(G) = ν(G') - ε(G') + φ(G')*,
and the result holds for *G* iff it holds for *G'*.

We now remove *k-1* of the edges traversing *C* in the embedding of *G'*.
This deletes *k-1* edges and *k-1* faces.
When we delete the final edge, we transform a face which is a *2*-cell into a face containing the crosscap,
but bounded by the cycle
*v*_{1}v_{2}...v_{2k}v_{1}.
We now remove this face and its crosscap
and replace the with the *2*-cell
bounded by *v*_{1}v_{2}...v_{2k}v_{1}.
The resulting graph, *G"* has
*ν(G") = ν(G')*,
*ε(G") = ε(G') - k*,
*φ(G') = φ(G) - (k-1)*, and is embedded on
*S*_{g,c-1}. Hence,
*ν(G') - ε(G') + φ(G') = ν(G") - ε(G") + φ(G") + 1 =
2 - 2g - (c-1) +1 = 2 - 2g - c*.

We may therefore assume that *c=0*.

For each handle *H = (H*_{1},H_{2}), we shall mimic the above process.
Suppose that *H* is a handle of *S*_{g,c} and that the the edges traversing *H* are
*e*_{1}, *e*_{2}, ..., *e*_{k}, in this cyclic clockwise order about
*H*_{1} (see Figure 4).
We add vertices *v*_{1}, *v*_{2}, ..., *v*_{k},
cyclically around (but slightly outside of) *H*_{1},
with *v*_{i} on *e*_{i} and
vertices *v*_{k+1}, *v*_{k+2}, ..., *v*_{2k},
cyclically around (but slightly outside of) *H*_{2},
with *v*_{k+i} on *e*_{i}.
This adds *2k* vertices and *2k* edges to the graph,
but does not effect the interior any face.
Now, add edges *v*_{1}v_{2}, *v*_{2}v_{3}, ...,
*v*_{k}v_{1}, and edges
*v*_{k+1}v_{k+2}, *v*_{k+2}v_{k+3}, ...,
*v*_{2k}v_{k+1} (see Figure 5).
Each edge that is added lies entirely within a face of the embedding,
and thus subdivides that face into two faces, each of which is a *2*-cell,
increasing the number of faces by one and the number of edges by one.
Each of these operations results in a connected graph.
Let *G'* denote the graph that is obtained after all of these operations. Then,
*ν(G') = ν(G) + 2k*,
*ε(G') = ε(G) + 4k*,
*φ(G') = φ(G) + 2k*,
*ν(G) - ε(G) + φ(G) = ν(G') - ε(G') + φ(G')*,
and the result holds for *G* iff it holds for *G'*.

Let *G*^{*} denote the subgraph which is obtained
by deleting all edges traversing any of the handles.
There is a natural embedding of *G*^{*} on *S*_{0}.
Each face of *G*^{*} is either a *2*-cell from the embedding of *G'*
or is one of the cycles we have added around the circular regions defining the handles
(and these faces also are *2*-cells). Thus, *G*^{*} is connected.
We may now proceed to remove the handle *H*.
When we delete the *k* edges traversing *H*,
we delete *k* faces which were *2*-cells, and leave a face that contains the handle.
We now delete this aberrant face and replace it by two *2*-cells, one with boundary
*v*_{1}v_{2}...v_{k}v_{1}, and the other with boundary
*v*_{k+1}v_{k+2}...v_{2k}v_{k+1}.
The resulting graph, *G"* is connected and has
*ν(G") = ν(G')*,
*ε(G") = ε(G') - k*,
*φ(G') = φ(G) - k + 2*, and is embedded on
*S*_{g-1}. Hence,
*ν(G') - ε(G') + φ(G') = ν(G") - ε(G") + φ(G") + 1 =
2 - 2(g-1) +2 = 2 - 2g*.

We may now assume that *g = c = 0* and that *G* is embedded on *S*_{0}.

Let *T* be any spanning tree of *G*.
There are *ε-ν+1* edges of *G* which are not in *T*.
Any such edge *e* is contained in a unique cycle *C*_{e} of *T+e*.
Since *C*_{e} forms a closed curve on the sphere,
the edge *e* is part of the boundary of two distinct faces of *G*,
separated by *C*_{e}.
If we delete *e*, we merge these two faces into a new *2*-cell,
decreasing the number of edges and the number of faces by one,
while leaving the number of vertices static.
Thus, we need only prove the result for trees embedded on the sphere.
But, here, *φ=1*, and *ε=ν-1* and the result is immediate.

**Bounded degrees on** *S*_{g}.

Suppose that *G* is a connected, simple graph embedded on *S*_{0}.
Then, the minimum degree of *G*, *δ(G)*, is at most 5.

Suppose that *G* is a connected, simple graph embedded on *S*_{g}, *g > 0*.
Then, *2δ(G) ≤ 5 + *sqrt*(1+48g)*.

**Proof**.

We may add edges, if necessary to obtain a *2*-cell embedding,
and thus *ν - ε + φ -2 + 2g = 0*.
Now, as long as there are at least three vertices, each face is bounded by at least three edges,
and hence,
*2ε ≥ 3φ = 3ε - 3ν +6 - 6g*. Rearranging, yields
*ε ≤ 3ν - 6 + 6g*.

In the case that *g = 0*, this says, *ε ≤ 3ν - 6*.
If, say, *δ ≥ 6*, then
*2ε ≥ νδ ≥ 6ν* is a contradiction. Thus, for the sphere, δ < 6.

We now consider the case in which *g > 0*.
Let us assume that *δ ≥ 6*, or there would be nothing left to prove.
(The astute reader should note where this condition is used later in the proof.)
Note also, *ν ≥ δ + 1*, since *G*, being simple, has no loops or multiple edges.
Now,

*δν ≤ 2ε ≤ 6ν - 12 + 12g*,

*(δ-6)ν ≤ 12g - 12*,

*(δ-6)(δ+1) ≤ 12g - 12*,

*δ*^{2} - 5δ - 6 ≤ 12g - 12,

*δ*^{2} - 5δ + 6 - 12g ≤ 0.

If we consider the equation *δ*^{2} - 5δ + 6 - 12g = 0,
we would solve for
*δ* and find that *2δ(G) = 5 ± *sqrt*(1+48g)*.

For the inequality, then, we have
*5 - *sqrt*(1+48g) ≤ 2δ(G) ≤ 5 + *sqrt*(1+48g)*, completing the proof.

**Heawood's Theorem**.
Suppose that *G* is a loopless graph embedded on *S*_{g}, *g > 0*.
Then, the chromatic number of *G*, *χ(G)*, is bounded by *(7 + *sqrt*(1+48g)) / 2*.

**Proof**. We replace any multiple edges by single edges,
since multiple edges carry no more information for the purposes of colouring.
Also, if *G* is disconnected, the result will follow by looking at each component of *G* separately.

Now, there is a vertex *w* of degree at most *(5 + *sqrt*(1+48g)) / 2*, and we can colour
*G-w* in at most *(7 + *sqrt*(1+48g)) / 2* colours by induction
(or trivially if *G* has only one vertex). Then, there is at least one colour remaining to be used at *w*.

Let *f*_{g} denote the integer part of *(7 + *sqrt*(1+48g)) / 2*.
We have only provided the proof that *f*_{g}
colours suffice for any loopless finite graph embedded on *S*_{g}, *g > 0*.
That some graph needs *f*_{g} colours was shown by
Ringel and Youngs,
by showing that *K*_{p}, *p ≥ 3*, embeds on a surface of genus *g*,
where *g* is the smallest integer which is at least *(p-3)(p-4)/12*.

That four colours suffice for finite graphs on *S*_{0}, see the proof by
Haken and Appel.

There are also results for graphs embedded on *N*_{c}, *c > 0*, *c ≠ 2*.
Let *h*_{c} denote the integer part of *(7 + *sqrt*(1+24c)) / 2*. Then,
*h*_{c} colours suffice and there are graphs on the surface which take this many colours.
Here,
*K*_{p}, *p ≥ 3*, *p ≠ 7*, embeds on *N*_{c},
where *c* is the smallest integer which is at least *(p-3)(p-4)/6*. The exception is that
*K*_{7} does not embed on *N*_{2}, the Klein bottle,
and every graph which can be embedded on the Klein bottle has chromatic number at most six.
(The astute reader might wish to verify that proof on this page can easily be extended to show that if *G* is any simple, but not complete, graph
embedded on *N*_{2}, then *G* has a vertex of degree at most five.)

The upper bounds for graphs on *N*_{c} or *S*_{g} are sometimes combined.
The chromatic number of a graph *G* embedded on one of these surfaces, *S*, is at most
*(7 + *sqrt*(49-24E*_{S} )) / 2,
where *E*_{S} is the Euler characteristic of *S*.
(The special case *E*_{S} = 2 is the Haken-Appel theorem.)

Back to the
Graph
Theory Index.

**
Department of Mathematical Sciences**

Florida Atlantic University

777 Glades Road

Boca Raton, Florida 33431-0991

USA**
Office: Room 286, Science & Engineering**

Phone: (561) 297-3350

Fax: (561) 297-2436

URL: http://math.fau.edu/locke/Heawood.htm

Last modified November 13, 2008, by S.C. Locke.