colorings of plane graphs

Colorings of plane graphs

This is the first draft of this write-up. Corrections of its contents and suggestions are welcomed.

A planar graphMathworldPlanetmath is a graph that can be embedded on a sphere or plane. A plane graph is such a graph together with a choice how to embed it; its faces are the resulting regions of surface separated by edges.

A (face, edge, vertex etc.) coloringMathworldPlanetmath is just a mapping from the relevant set of items to a small set of other things traditionally given the names of colors.

In graph theoryMathworldPlanetmath however there is usually an extra condition a coloring has to satisfy to be valid. Unless specified otherwise, the condition is that adjacentPlanetmathPlanetmathPlanetmath items must be given distinct colors — two edges meeting at a vertex must have different colors, two faces with a common border must too.

Face colorings

Because of the history of the subject, being couched in terms of coloring maps, faces have often been called “countries” and the plane graph a “map”.

A word on “border” in the context of face coloring. For countries to be considered adjacent it is not enough to just meet at one point. The reason is that that would make coloring problems uninteresting: divide a region into as many countries as you want, arranged like a pie chart, and any number of colors would be required if touching at a point did qualify.

So in a map which has a portion shaped like ×, both the North and South countries border both the East and West countries, but South does not border North so they’re allowed to have the same color, and West is likewise allowed to have the same color as East. Now consider a small border adjustment from × to >-< where we’ve added one extra constraint: now North and South must have different colors. If it was possible to color the old map with a certain number of colors we can’t be certain we can still color the new map. Conversely however, if we can color the new map we can certainly color the old map (using the same color assignment even).

If we are given any bridgeless planar graph G (not necessarily trivalent), we can give any vertex with valencyPlanetmathPlanetmath 4 this treatment, splitting it into two new vertices of valency 3 and a short new stretch of border, adding a constraint on coloring. Vertices with valency v>4 can be given the same treatment in v-3 steps, creating v-2 vertices of valency 3 and v-3 new pieces of border which only makes the problem harder: if we can still color this, we can also color the original.

2-valent vertices are simply funny features along an ongoing border between two countries, and 0-valent vertices funny features within the landscape. Removing them does not alter the coloring exercise. And finally 1-valent vertices create a bridge; we do not want them nor do we want any other bridges, because at such an edge a country meets itself on the other side of the border, making it impossible to have a color change there. This is why face coloring theoremsMathworldPlanetmath are stated for bridge-free graphs only.

By now we have only vertices left of valency 3 so our new graph G𝖸 is trivalent (cubic). And if it can be n-colored (for any n), then so can G. This completesPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the proof of

Lemma 0 Any bridge-free planar graph can be 4-colored any bridge-free planar trivalent graph can be 4-colored.

as the direction was argued above, and the direction is immediate (any includes all the trivalent ones). 

Note the lemma does not state either side of the “iff” is true, merely that they are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. The left-hand side is known as the four-color theorem; having the right-hand side equivalent to it gives statements on trivalent graphs a more general importance.

One last point: we will consider the graph drawn on a sphere. Or, what is the same thing: if we draw it on a plane, we will also consider the infiniteMathworldPlanetmath outside area to be a face. If you were thinking of your graph as a map subdividing a finite continent into countries just call the outside Oceania and color it blue.

This convention too only makes the coloring harder: considering the outside to be a colorless sea allows countries with a shoreline to be of all four colors, while coloring Oceania (say) blue only allows those countries three different colors (just like any other set of countries with a common neighbour). Again, if we can color this, we can color plane maps of any other convention.

Edge colorings

A Tait coloringMathworldPlanetmath of a trivalent graph is a coloring of its edges with only three colors, such that at each vertex the colors of the three edges there are different. After Peter G. Tait (1831–1901), Scottish physicist ( at St Andrews), who in 1880 proved the following

Theorem 1 (Tait) A bridge-free trivalent plane graph can be face-colored with 4 colors if and only if it can be edge-colored with 3 colors.

We will not give our four colors such poetic names as red or green, instead they will be given two-bit labels (0,0) and (0,1) and (1,0) and (1,1), formally vectors in 𝖨𝖥22, the vector space of dimensionMathworldPlanetmath 2 over the finite field of order 2.

Edge colors used will be the differencePlanetmathPlanetmath between the face colors on either side of the edge. Because 𝖨𝖥22 has characteristic 2, differences are the same thing as sums (so it doesn’t matter which we subtract from which). They are carried out (mod 2) on the individual coördinates (in terms of bit patterns: additionPlanetmathPlanetmath without internal carry, that is, the xor operationMathworldPlanetmath).

Note that the assignment of labels to face colors is quite arbitrary (e.g. (0,0) has no special significance) but the assignment to edge colors is less arbitrary: here 𝟎=(0,0) really means something. It means a border between faces of the same color, exactly the thing that shouldn’t happen. You could say face colors are “position vectors” (where (0,0) is an arbitrary point) while edge colors are “free vectors”, differences between position vectors.

Proof of : let F and E be the sets of faces and edges, let f:F𝖨𝖥22 be a valid face-4-coloring, and g:E𝖨𝖥22 the edge coloringMathworldPlanetmath we are trying to construct from f. Let e be any edge, and α and β the faces it separates. Now f being valid means f(α)f(β) so g(e)=f(α)-f(β)𝟎. This means g really is an edge-3-coloring g:E𝖨𝖥22{𝟎}.

It is also easy to see g is a valid coloring: let d and e be any two edges meeting at vertex p say, and let α, β and γ be the three faces found around p such that e separates α and β, and d separates α and γ. By f being valid we have f(β)f(γ) from which g(e)=f(β)-f(α)f(γ)-f(α)=g(d)

Note in passing that the three edge colors around p all being different (and nonzero) means they must be (0,1), (1,0), (1,1) in some order. That means they sum to 𝟎 in a valid edge-3-coloring, a result we will use.

To construct f from g you might pick a color, give it to the country you’re in, and travel the world. At each border, add its edge color to the previous face color and assign that to the new country. I called edge colors differences rather than sums for that reason: if a journey Γ visits faces αβγψω, and the face colors everywhere have to be such that the edges crossed have colors f(β)-f(α), f(γ)-f(β), … f(ω)-f(ψ) then the color f(ω) reached should be f(α)+ colors of edges crossed.

So we construct f by “integrating” g (and indeed, “plus a constant”, the arbitrary color of the first country). If we can do that without contradictionMathworldPlanetmathPlanetmath between all possible journeys, this “potential” f will automatically have g as its “gradient” as it should. Remains to prove the “integral” is independentPlanetmathPlanetmath of path taken, in other words that circular paths “integrate” to zero.

Thus far we haven’t used the fact that we’re in a sphere or plane! Of course, the use of “faces” at all means we have an embeddingMathworldPlanetmathPlanetmath of a graph in some surface; the fact we didn’t use yet is that the surface has genus 0. Indeed, the forward half of Tait’s theorem (valid f implies valid g) is true in surfaces of any genus. For the reverse half (valid g implies valid f) we need to use the topological properties of the plane or sphere.

There are various ways of doing that. One wonderfully simple proof found in Wilson [Wil02], adapted here to use the 𝖨𝖥22 notation, relies on the graph being embedded in a plane. For a graph embedded in a sphere that entails choosing a country and puncturing the sphere in the interior of that country; it corresponds to the choice of giving that country the face color (0,0).

Proof of : the subgraphMathworldPlanetmath G formed by edges of the two colors (1,any) is regularPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath 2-valent. So is the subgraph G′′ formed by edges of the two colors (any,1). Such graphs consist of disjoint cycles. In a plane, such cycles have a well-defined interior and exterior. Every face α has a number g counting the number of (nested) cycles of G it is inside, and similarly a number g′′ with respect to G′′.

Let r and r′′ be the residues of g and g′′ (mod 2). Give the face the color (r,r′′). This is clearly a face-4-coloring. And it is valid: to reach any neighbouring face β we cross an edge with color (e,e′′) where e=1 iff β is inside a number of G cycles that differs by 1 from g, likewise e′′=1 iff β is inside a number of G′′ cycles that differs by 1 from g′′. So β has color (r+e,r′′+e′′) and we know e and e′′ are not both zero. 

Tait himself hoped to prove face-4-colorability, via edge-3-colorability, in the following way.

Lemma 2 (Tait) A trivalent plane graph that has a Hamiltonian cycleMathworldPlanetmath can be edge-colored with 3 colors.

A Hamiltonian cycle is a closed path that visits every vertex exactly once (and yes, that Hamilton). We dropped the “bridgeless” qualifier because having a cycle in which every vertex is involved means no bridges: for any vertices p and q you can travel between them via the Hamiltonian cycle, and back via all different edges using the other half of the cycle. That would be impossible with a bridge: pick p and q either side of the bridge, now two routes between them would have to use the same edge (that bridge).

Note also that in a trivalent graph the number of edges m equals 3n/2 where n is the number of vertices. But m is an integer, so n is even.

Proof of lemma: the Hamiltonian cycle, having n vertices, also has n edges, which is even. Color them alternatingly red and green. Each vertex now has one red and one green edge; color the third edge blue. 

So Tait next tried to prove every planar graph has a Hamiltonian cycle. Unfortunately, some don’t.

A vertex coloring

Curiously, the property that a graph is face-4-colorable, which turned out to be equivalent to being edge-3-colorable by Tait’s theorem, is also equivalent to admitting a certain kind of vertex-2-coloring. This seems to have been discovered independently a few times, most notably by Percy J. Heawood ( at St Andrews).

We can call the vertex colors black and white, but think of them as representing values +1 and -1 interpreted as residues (mod 3). This is not the kind of coloring where adjacent items have to be of different color! It does have another more global constraint though: around any face, the vertex colors must sum to 0 (mod 3).

Theorem 3 A bridge-free trivalent plane graph can be edge-colored with 3 colors if and only if it can be vertex-colored in the way just explained.

Rename the three edge colors to 0, 1 and 2 interpreted as residues (mod 3). These are again “position vector”-like; there’s no special significance to being 0. Let g3 be this new relabeled verion of the old g.

We construct a vertex coloring h3:V{+1,-1} from g3 as follows: assign color +1 to a vertex if the edges there have colors 0, 1, 2 going clockwise; -1 if counterclockwise. If the edge coloring g3 is valid, it is possible to define an h3 this way.

Note this makes the vertex colors differences of edge colors in the following sense. If we travel around a face counterclockwise (i.e. always turning left) and d and e are two successive edges joined at vertex p, then g3(e)-g3(d)=h3(p). If instead we turn right to edge x say, we get g3(x)-g3(d)=-h3(p).

Proof of : Based on g3, define h3 as above. To prove it is valid. Pick any face α, and any edge e in it, let g3(e)=c. Go round the face counterclockwise one whole cycle. Now


(mod 3). Which proves the sum of h3 values around the cycle is zero. 

The same argument works in reverse: if h3 is a valid vertex coloring then, in any one cycle, we could assign an arbitrary color c to an edge e and, going round counterclockwise finding vertices p, q… we could assign to the edges after e the colors c+h3(p), c+h3(p)+h3(q), and so on. Because h3 sums to zero around the cycle, it consistently assigns edge colors (e.g. edge e again gets color c once around the cycle) and because h3 is never zero, we never get the same edge color for successive edges.

But this isn’t yet enough. Given an h3 satisfying its rule, we can start reconstructing g3 by this “integration” process. We just saw it works locally on the level of single face boundary cycles. As with the previous theorem however, the problem with “integrating” is to prove this can be done unambiguously on a global scale, for which the topological properties of genus 0 surfaces must again crop up somehow.

I will choose to use the following property of planes and spheres:

Lemma 4 With a plane graph of u faces on a genus 0 surface, it is possible to enlarge a collectionMathworldPlanetmath of 1 face to u-1 faces, one face at a time, in such a way that the area covered remains simply connected throughout.

Simply connected means that the area covered is topologically equivalent to a disk, that it doesn’t enclose any isolated area. Its boundary is a simple closed curve. Imagine the area covered by the collection of faces as shaded. On a sphere, the area covered being simply connected means there is a single connectedPlanetmathPlanetmath shaded area inside the boundary and a single connected unshaded area outside, and that the boundary is one closed curve. Of course, while the outside starts off big, it is reduced to just one face by the time the inside has reached u-1 faces.

Proof of lemma: start with one face shaded. At each stage, there will be other faces immediately bordering the area shaded thus far. Choose one, call it α. If accreting it to the side of the growing shaded area would leave it simply connected, take it and move to the next step.

Now suppose α misbehaves, that adding it would enclose (one or more) unshaded region(s) . Of course on a sphere we are already enclosing an unshaded region, the whole outside. So what is really happening if α misbehaves is that adding it would split the remaining outside into two (or more) pieces. Choose any one of those pieces and let that be our region .

Note that each of those pieces, including , contain some faces that border the already shaded area. The way it works is this: The boundary of the shaded region has k stretches where it borders α, and k1 because α was chosen as a face that borders the shaded area. If k=1 it doesn’t misbehave; if k>1 then adding it would split the new outside into k regions: in between the k stretches where the shaded area borders α there are k stretches where each time it would border one of those regions.

Choose a face β from the faces of that border the shaded region, and try adding it. If that would fail too it would be by splitting the outside in more than one region. Choose one of those that does not contain α and call it . Because it does not include α, it is wholly contained within one of the regions adding α would have created, namely . In fact {β} i.e. it has at least one fewer country than .

Choose a face γ from the faces of that border the shaded region, if this doesn’t work either choose a ′′ that does not contain β, and so on.

Now only has finitely many faces, and ||>||>|′′|. So things can go wrong only a finite number of times. We end up with a country that can be added without budding off a piece of outside. 

Now we can finish our proof of Theorem 3.

Proof of : Pick one face. We saw we could pick an arbitrary color for one of its edges and then continue assigning g3 colors based on h3 going round, in a valid way. Shade the face to mark it as “done”.

Now pick additional faces along the lines of lemma 4. Keeping the boundary of the shaded area simply connected means that each new face borders the previous shaded area along a single stretch of boundary (say edges am going counterclockwise), and this means the portion of the boundary of the new face where the edges (nz say) don’t have colors yet is also a single stretch.

This means we can edge-color the additional face validly: give a the color it already has, and go round turning left each time assigning edge colors based on h3. This must agree with the colors for bm we already assigned consistently, and gives new colors for nz (which are now also consistent with the rest) and gives the same color again to a because h3 is valid.

Once we have covered u-1 faces, the last face already has all its edges colored, validly. 

It’s a pity there doesn’t seem to be an easy way to find such a vertex coloring from scratch (thereby making the four color theorem much more simple to prove). There cannot be a very obvious way to find one. For example, valid face-4-colorings and edge-3-colorings of the dodecahedronMathworldPlanetmathPlanetmath correspond to a vertex-2-coloring that uses 4 of one color and 16 of the other color. It’s hard to see how any automatic scheme could spontaneously break the symmetryMathworldPlanetmathPlanetmath and treat 4 of those 20 vertices differently.

The four-color theorem says every bridgeless trivalent plane graph has a valid face-4-coloring. It is equivalent to saying it has a valid edge-3-coloring. And now it is equivalent to saying it has a valid vertex-2-coloring. The next thing would be a valid something-1-coloring, and it shouldn’t be too hard to prove that things can all be colored with 1 color! Unfortunately, we seem to have run out of graph elements to take the place of that “something”.

A corollary: 3n-gon faces

Consider a valid vertex-2-coloring h3, with some black (+1) and some white (-1) vertices. Around each face, they sum to 0 (mod 3).

Now consider the following modification: pick any vertex, and replace it by a tiny triangular country. If we give the three new vertices the opposite color from the old vertex, the coloring is still valid (in each of the three adjoining faces, one ±1 is replaced by two 1 which counts as the same).

Conversely, if the graph had any triangleMathworldPlanetmath face we could replace it by a single vertex. The only way three +1 or -1 can add to zero (mod 3) is if they were all of the same sign, so we replace it by one vertex of the opposite sign.

Now suppose we expand all white vertices to black triangles. Or vice versa. We saw each single modification leaves a valid vertex coloring valid. So once we’re done and only have vertices of the same color, the coloring must still be valid. That can only mean one thing: every face now has a number of vertices divisible by 3. Not only the triangles we added, but also the original faces, which must have grown to 6-, 9-, 12- etc. -gons.

Theorem 5 A valid vertex coloring as in Theorem 3 exists if and only if it is possible to modify the plane graph, turning some vertices into triangles, in such a way that we end up with only faces whose size is divisible by 3.

Proof of : We just did it. 

Proof of : We are given such a sequence of modifications where every face ended up as a 3n-gon. It is very easy to give this a valid vertex-2-coloring: just give every vertex the same color. Now undo the modification step by step, each time coloring the new single vertex the opposite color from the triangle it replaced. Modifications and their reversals preserve the validity of vertex-2-colorings, so by the time we have undone every modification the graph is still validly colored. 

This gives yet another corollary of the four color theorem: that we can always find such a modication to 3n-gon faces.


The dual G* of a bridgeless plane graph G is formed as follows: place one vertex of G* inside each face of G. For each edge e of G, separating faces α and β, draw one edge of G* from its vertex in α to its vertex in β, in such a way that the only edge of G it crosses is e, and so that it crosses e at a point other than its endpointsMathworldPlanetmath.

This construction creates faces of G* that each enclose one vertex of G and every one of those vertices is thus enclosed, making G likewise a dual of G*.

To prove that assertion: let p be a vertex of G, surrounded by faces α, β and with edges d, e radiating from it. All those edges will be crossed by edges of G* forming a closed cycle because they connect the vertices of G* placed inside α, β going round. There are no other edges of G* crossing our edges, and no edges of G nearer to p to cross, so the cycle forms the boundary of a face. This shows every vertex of G has a dual face of G*.

To show every face of G* is now accounted for, we can invoke Euler’s formulaMathworldPlanetmath. G has n vertices, m edges, f faces, with n-m+f=2. For G* we have by construction n*=f vertices, m*=m edges, and an unknown number f* of faces. By the previous argument there are at least the n faces with vertices of G in it. But by n*-m*+f*=2 (and n*=f and m*=m and n-m+f=2) f* must equal that n

Modern formulations of the four color theorem usually take the dual view. In stead of a face-4-coloring, a vertex-4-coloring. Note this is different from the vertex-2-coloring in the previous sectionsMathworldPlanetmathPlanetmath; it has the standard constraint that adjacent verticesMathworldPlanetmath must have different colors.

The dual expression of lemma 0 is now that it is sufficient to consider plane graphs where every face is triangular (the dual of the × to >-< machinations is tiling up a v-gon into v-2 triangles).


The subject has colorful beginnings. Francis Guthrie was born in England in 1832, obtained firsts in both mathematics and law, taught mathematics in South Africa until his death in 1899 and also found the time to get involved with railroad construction and to make his name in botany. One day he noticed something when coloring a map of the counties of England — the original four-color conjecture. And on 23 October 1852, in London, his brother Frederick asked his own math professor Augustus de Morgan about that observation (“With my brother’s permission”). De Morgan consulted Hamilton (“A student of mine asked me to day to give him a reason for a fact which I did not know was a fact — and do not yet.”). The latter didn’t think much of it and quipped he didn’t have time for that “quaternion of colours”. The problem didn’t go away though, Cayley dug it out again, Kempe gave his flawed proof that stood for 11 years, and the rest is history [FW77, FF94].

The four-color conjecture (now four-color theorem) has loomed large over graph theory. The story how Kenneth Appel, Wolfgang Haken and John Koch found the proof by computer in 1976 is well known. Perhaps it has been fortunate the theorem resisted proof so long, because it has been a motivating force for many exciting developmentsMathworldPlanetmath in graph theory. This includes important results in graph coloring such as Vizing’s theorem, but also work that transcends the bounds of graph theory, such as that by Whitney and Tutte on what is now called matroidsMathworldPlanetmath.

And the future? Hadwiger’s conjecture can be regarded as a generalisation of the four-color theorem. And it is still open.


  • 1
  • Ore67 Oystein Ore, The Four-Color Problem,
    Acad. Pr. 1967 without ISBN  0 12 528150 1
    Long the standard work on its subject, but written before the theorem was proven. Has a wealth of other graph theory material.
  • FW77 S. Fiorini and R. J. Wilson, Edge-colourings of graphs
    (Research notes in math. 16), Pitman 1977, ISBN  0 273 01129 4
    The first ever book devoted to edge-colorings, including material previously found only in Russian languagePlanetmathPlanetmath journal articles.
  • SK77 Thomas L. Saaty and Paul C. Kainen,
    The Four-Color Problem: assaults and conquest,
    McGraw-Hill 1977; repr. Dover 1986, ISBN  0 486 65092 8
    Wonderfully broad, not only focussing on the now standard route to the Appel-Haken proof but also giving a wealth of other material related to colorings.
  • FF94 Rudolf Fritsch and Gerda Fritsch,
    Der Vierfarbensatz, Brockhaus 1994;
    The Four-Color Theorem, tra. Julie Peschke,
    Springer 1998, ISBN  0-387-98497-6
    History of the theorem with biographical cameos by G. Fritsch, thorough topological treatment of plane graph embedding and details of the Appel-Haken proof by R. Fritsch.
  • Wil02 Robert A. Wilson, Graphs, Colourings and the Four-colour Theorem, Oxford Univ. Pr. 2002, ISBN  0 19 851062 4 (pbk), raw/graph.html raw/graph.html (errata &c.)
    A good general course in graph theory, with special focus on the four-color theorem and details of the Appel-Haken proof.
Title colorings of plane graphs
Canonical name ColoringsOfPlaneGraphs
Date of creation 2013-03-22 15:10:25
Last modified on 2013-03-22 15:10:25
Owner marijke (8873)
Last modified by marijke (8873)
Numerical id 8
Author marijke (8873)
Entry type Topic
Classification msc 05C15
Related topic FourColorConjecture
Related topic TaitColoring
Related topic KempeChain