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 S0. A graph G is embedded on S0 if the vertices of G are points of S0, the edges of G are continuous (and smooth) arcs on S0, 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 Nc. The projective plane is N1. The Klein bottle is N2.
Figure 1


A handle may be considered as a disjoint pair of circular regions H1 and H2. If the edges entering H1 are listed cyclically clockwise as e1, e2, ..., ek, then these emerge at H2 in the same cyclic ordering, but counterclockwise (see Figure 4). A surface with g pairwise disjoint handles is frequently referred to as Sg. The torus is S1.

The Euler characteristic of Sg is 2 - 2g, and the Euler characteristic of Nc is 2 - c.

In these notes, a surface with g handles and c crosscaps, pairwise disjoint, will be denoted Sg,c.



Euler's Theorem and generalization. Let G be a finite, connected graph embedded on a surface Sg,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 Sg,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 Sg,c and that the the edges traversing C are e1, e2, ..., ek, e1, e2, ..., ek, in this cyclic order. Each edge is listed twice, since it enters and leaves at diametrically opposite points of C. We add vertices v1, v2, ..., v2k, cyclically around (but slightly outside of) C, with vi and vk+i on ei (see Figure 2).
Figure 2
This adds 2k vertices and 2k edges to the graph, but does not effect the interior of any face. Now, add edges vivi+1, subscripts modulo 2k (see Figure 3).
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 v1v2...v2kv1. We now remove this face and its crosscap and replace the with the 2-cell bounded by v1v2...v2kv1. The resulting graph, G" has ν(G") = ν(G'), ε(G") = ε(G') - k, φ(G') = φ(G) - (k-1), and is embedded on Sg,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 = (H1,H2), we shall mimic the above process. Suppose that H is a handle of Sg,c and that the the edges traversing H are e1, e2, ..., ek, in this cyclic clockwise order about H1 (see Figure 4).
Figure 4
We add vertices v1, v2, ..., vk, cyclically around (but slightly outside of) H1, with vi on ei and vertices vk+1, vk+2, ..., v2k, cyclically around (but slightly outside of) H2, with vk+i on ei. This adds 2k vertices and 2k edges to the graph, but does not effect the interior any face. Now, add edges v1v2, v2v3, ..., vkv1, and edges vk+1vk+2, vk+2vk+3, ..., v2kvk+1 (see Figure 5).
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 S0. 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 v1v2...vkv1, and the other with boundary vk+1vk+2...v2kvk+1. The resulting graph, G" is connected and has ν(G") = ν(G'), ε(G") = ε(G') - k, φ(G') = φ(G) - k + 2, and is embedded on Sg-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 S0.

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 Ce of T+e. Since Ce forms a closed curve on the sphere, the edge e is part of the boundary of two distinct faces of G, separated by Ce. 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 Sg.
Suppose that G is a connected, simple graph embedded on S0. Then, the minimum degree of G, δ(G), is at most 5.
Suppose that G is a connected, simple graph embedded on Sg, 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 Sg, 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 fg denote the integer part of (7 + sqrt(1+48g)) / 2. We have only provided the proof that fg colours suffice for any loopless finite graph embedded on Sg, g > 0. That some graph needs fg colours was shown by Ringel and Youngs, by showing that Kp, 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 S0, see the proof by Haken and Appel.

There are also results for graphs embedded on Nc, c > 0, c ≠ 2. Let hc denote the integer part of (7 + sqrt(1+24c)) / 2. Then, hc colours suffice and there are graphs on the surface which take this many colours. Here, Kp, p ≥ 3, p ≠ 7, embeds on Nc, where c is the smallest integer which is at least (p-3)(p-4)/6. The exception is that K7 does not embed on N2, 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 N2, then G has a vertex of degree at most five.)

The upper bounds for graphs on Nc or Sg are sometimes combined. The chromatic number of a graph G embedded on one of these surfaces, S, is at most (7 + sqrt(49-24ES )) / 2, where ES is the Euler characteristic of S. (The special case ES = 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://www.math.fau.edu/locke/Heawood.htm

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