Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 73–77
A new proof of 3-colorability of Eulerian
triangulations∗
Mu-Tsun Tsai , Douglas B. West †
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA
Received 24 May 2010, accepted 5 October 2010, published online 7 March 2011
Abstract
Using the existence of noncrossing Eulerian circuits in Eulerian plane graphs, we give
a short constructive proof of the theorem of Heawood that Eulerian triangulations are 3-
colorable.
Keywords: Plane triangulation, Eulerian circuit, 3-colorable, Heawood’s Theorem.
Math. Subj. Class.: 05C10, 05C45, 05C15
1 Introduction
The “Three Color Problem” is the question of which planar graphs can be vertex-labeled
from a set of three colors so that adjacent vertices have distinct colors, making them 3-
colorable. Stockmeyer [15] proved that it is NP-complete to determine whether a planar
graph is 3-colorable, so it is likely that no nice characterization exists. Attention has there-
fore focused on finding sufficient conditions for 3-colorability. For example, Grötzsch’s
Theorem [5] states that triangle-free planar graphs are 3-colorable.
It was claimed in the 19th century that triangulations (plane graphs in which every
face is a triangle) are 3-colorable if (and only if) every vertex has even degree, but no
complete proof was published until much later. The claim holds more generally for near-
triangulations in which every vertex has even degree, where a near-triangulation is a planar
multigraph whose bounded faces are all 3-cycles. Over the years, the statement has been
proved and reproved in a variety of ways. In this note, we provide a new proof that is quite
different from the previous proofs. We summarize the history and two previous proofs, for
comparison.
A connected graph with all vertex degrees even is Eulerian, meaning that it has a single
circuit (closed trail) traversing all the edges. Our proof uses the fact that Eulerian plane
∗Dedicated to the memory of Michael O. Albertson
†Research partially supported by the National Security Agency under Award No. H98230-10-1-0363.
E-mail addresses: tsai39@illinois.edu (Mu-Tsun Tsai), west@math.uiuc.edu (Douglas B. West)
Copyright c© 2011 DMFA Slovenije
74 Ars Math. Contemp. 4 (2011) 73–77
graphs have “non-crossing” Eulerian circuits. We show that in a near-triangulation, cycling
through the colors 1, 2, 3 along such a circuit produces a proper 3-coloring. We also use
the fact that the number of edges of any Eulerian near-triangulation is divisible by 3. These
two lemmas are known facts with very short proofs.
One can view our proof as a fast algorithm to produce the coloring, but in fact once one
proves 3-colorability the independent sets in a proper 3-coloring of an Eulerian triangula-
tion are immediately unique; as one travels from face to face, the vertices that complete
two bounded faces sharing an edge must be in the same independent set.
2 The history
The 3-colorability of Eulerian triangulations is first claimed in the 1879 paper of Kempe [8,
p. 200], where he wrote (without proof):
If, excluding island and peninisula districts from the computation, every district is in
contact with an even number of others along every circuit formed by its boundaries,
three colours will suffice to colour the map.
Kempe omitted the condition that the dual of the map be a triangulation (in his language,
“exactly three boundaries meet at every point of concourse”). The statement fails without
that condition, since the Eulerian plane graph in Figure 1 is not 3-colorable. (A plane graph
is a particular embedding of a planar graph in the plane.)
•
••
•
•
•
•
Figure 1: A non-3-colorable Eulerian plane graph
As we have noted and will prove, all Eulerian near-triangulations are 3-colorable. In
1898, Heawood [6] asserted this statement, without proof. In 1939, Franklin [3] developed
relevant concepts foreshadowing the notion of nowhere-zero flows, but he did not complete
a proof of Heawood’s claim. Tutte [16, 17] later developed the basic theory of nowhere-
zero flows, and Steinberg [14] proved Heawood’s claim in 1993 using these methods.
Perhaps the first complete proof for triangulations (not near-triangulations) appeared in
1963. Golovina and Yaglom [4, p. 33] gave a proof by induction on the number of vertices.
In modern language, it can be sketched as follows. In an Eulerian plane triangulation G,
the minimum degree is 2 or 4. If G 6= K3, then a vertex v of degree 2 lies in two triangles
with its neighbors; replacing these triangles with a single edge joining the neighbors of v
yields a smaller Eulerian triangulation whose proper 3-colorings extend easily to G.
With a vertex v of degree 4 having neighbors w, x, y, z in cyclic order in the embedding,
the idea is that {w, y} or {x, z} consists of two distinct nonadjacent vertices. A pair of
opposites (say {w, y}) having this property can be contracted into v, keeping one copy of
the resulting three edges joining v to each of x and z. The result is a smaller Eulerian
triangulation G′, which has a proper 3-coloring f . Since x and z are at even distance in the
M.-T. Tsai and D. B. West: A new proof of 3-colorability of Eulerian triangulations 75
cycle of neighbors of v in G′, we have f(x) = f(z). To obtain a proper 3-coloring of G,
give w and y color f(v), and give v the third color. (The same argument holds when v is
on the unbounded face; alternatively, one can redraw the triangulation with some triangle
not containing v as the unbounded face.)
Another proof (see Lovász [10] and Shen [12]) rests on the 2-colorability of the ge-
ometric dual of an Eulerian plane multigraph G; that is, G is 2-face-colorable. Given a
proper 2-coloring of the faces by colors c and c′, one produces a proper 3-coloring of G so
that 1, 2, 3 appear in clockwise order around faces colored c and in counterclockwise order
around faces colored c′. In the main case, the edges of a triangular face F sharing one edge
with the unbounded face are deleted to form a graph G′ with fewer bounded faces. The
newly-external edges lie on bounded faces having the same color as F , say c. In the col-
oring of G′ given by the induction hypothesis, the clockwise order on these faces yields a
coloring of the vertices of F that obeys the clockwise requirement, completing the desired
coloring of G.
M. Kontsevich gave a surprisingly short proof (presented in [11]) using concepts in
topology. There have also been various extensions of the result. Król [9] extended the
result to show that a planar graph is 3-colorable if and only if it is a subgraph (not nec-
essarily spanning) of an Eulerian triangulation ([15] implies that testing that condition is
NP-complete). Hutchinson [7] studied generalizations to higher surfaces.
3 Proof by Eulerian circuits
One reason for sketching the Golovina–Yaglom proof above is the contrast between when
it and our proof apply. Without enhancements, their proof applies only to triangulations,
while ours requires the generality of near-triangulations to make the induction work.
We also use the interesting fact that an Eulerian graph embedded in the plane has an Eu-
lerian circuit that never crosses itself. A crossing in an Eulerian circuit C of a plane graph
consists of four edges e, e′, f, f ′ at a single vertex v such that e′ follows e and f ′ follows
f on C, and such that {e, e′} alternates with {f, f ′} in the cyclic rotation of edges incident
to v in the embedding. A noncrossing circuit has no such quadruple of edges. Visually, if
each vertex v splits into d(v)/2 vertices (d(v) denotes the degree of v), each inheriting two
edges incident to v that are consecutive in C, then the embedding of a noncrossing Eulerian
circuit becomes a simple closed curve in the plane.
The existence of noncrossing Eulerian circuits in Eulerian plane graphs was proved
by Abrham and Kotzig [1]. A shorter proof by Grossman and Reingold, independently,
appeared in response to a Monthly problem [13]. We give a slightly different approach.
Lemma 3.1. Every Eulerian plane graph has a noncrossing Eulerian circuit.
Proof. Let C be an Eulerian circuit with the fewest crossings. Suppose that {e, e′} and
{f, f ′} form a crossing, with e′ following e and f ′ following f . Reversing the part of C
from e′ to f (making f follow e and e′ follow f ′) eliminates this crossing and does not
increase the number of other crossings. To see this, only crossings at v need be considered,
since no other pairings change. New crossings must involve {e, f} or {f ′, e′}. Any visit to
v that crosses {e, f} or {f ′, e′} also crossed {e, e′} or {f, f ′}, and a visit that crosses both
new pairings crossed both of the old pairings. In particular, we have mapped new crossings
to distinct old crossings that are no longer present. Hence by the choice of C there is no
crossing.
76 Ars Math. Contemp. 4 (2011) 73–77
The external edges and external vertices in a plane graph are the edges and vertices of
the unbounded face. A graph is trivial if it has no edges.
Lemma 3.2. In every Eulerian near-triangulation, the number of edges is divisible by 3.
Proof. We use induction on the number of bounded faces. Given a nontrivial Eulerian
near-triangulation G, let F be a bounded face containing an external edge. Form G′ from
G by deleting the three edges of F . Since G′ is a disjoint union of smaller Eulerian near-
triangulations, the induction hypothesis implies that its number of edges is divisible by 3,
and hence the same holds for G.
It is also well known that the number of external edges is divisible by 3. This follows
from 2m = 3f+l, where m is the total number of edges, f is the number of bounded faces,
and l is the number of external edges. However, we do not need this fact. A subcircuit of a
circuit C is the portion of C between two visits to a particular vertex; a subcircuit is also a
circuit. The subtlety our proof must address is that a subcircuit of a noncrossing Eulerian
circuit need not traverse all the edges contained in its interior.
Lemma 3.3. In a noncrossing Eulerian circuit of an Eulerian near-triangulation, the
length of every subcircuit is divisible by 3.
Proof. Let C ′ be a subcircuit of a noncrossing Eulerian circuit C in an Eulerian near-
triangulation G. We use induction on the number of faces enclosed by C ′; if there is only
one such face, then the length is 3. Let v be the first and last vertex of C ′. Let H be the
subgraph of G consisting of all vertices and edges of C ′ and all vertices and edges of G
contained in the interior of C ′. If C ′ traverses all of H , then since C ′ is a circuit, it follows
that H is an Eulerian near-triangulation, and by Lemma 3.2 the length is divisible by 3.
Otherwise, other portions of C enter the interior to traverse the other edges of H (every
external edge of H is in C ′). The penetration may be at v or at another external vertex of
H that is visited more than once by C ′. Since C ′ is noncrossing, each such portion of C
must leave the interior at the same external vertex of H where it enters. It thus contributes
even degree at each vertex of H . We conclude that H is an Eulerian near-triangulation, so
its number of edges is divisible by 3.
Since each incursion by the rest of C into the interior of H departs by the same vertex
where it enters, it forms a subcircuit of C that encloses fewer faces than C ′. By the induc-
tion hypothesis, its length is divisible by 3. Hence subtracting the lengths of all incursions
from the size of H to obtain the length of C ′ leaves a multiple of 3.
Theorem 3.4. Every Eulerian near-triangulation is 3-colorable.
Proof. Let C be a noncrossing Eulerian circuit of an Eulerian near-triangulation G. Assign
colors to vertices while traversing C, cycling through colors 1, 2, 3. Every return to a vertex
previously colored completes a subcircuit of C. By Lemma 3.3, its length is a multiple of
3, and hence the same color is assigned. Thus the coloring is consistent, and it explicitly
assigns distinct colors to the endpoints of every edge.
References
[1] J. Abrham and A. Kotzig, Construction of planar Eulerian multigraphs, Proc. Tenth Southeast-
ern Conf. Comb., Graph Theory, and Computing (1979), 123–130.
M.-T. Tsai and D. B. West: A new proof of 3-colorability of Eulerian triangulations 77
[2] R. G. Busacker and T. L. Saaty, Finite Graphs and Networks: an Introduction with Applica-
tions, McGraw–Hill Book Co., 1965.
[3] P. Franklin, The Four Color Problem, Scripta Math. 6 (1939), 149–156.
[4] L. I. Golovina and I. M. Yaglom, Induction in Geometry (translated and adapted from the 2nd
Russian edition by A. W. Goodman, and O. A. Titelbaum), D. C. Heath & Co., 1963.
[5] H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-
U., Halle-Wittenberg, Math.-Nat. Reihe 8 (1959), 109–120.
[6] P. J. Heawood, On the four-colour map theorem, Quart. J. Pure Appl. Math. 29 (1898), 270–
285.
[7] J. Hutchinson, Three- and four-coloring nearly triangulated surfaces, Congr. Numer. 150
(2001), 129–143.
[8] A. B. Kempe, on the geographical problem of the four colours, Amer. J. Math. 2 (1879), 193–
200.
[9] M. Król, On a sufficient and necessary condition of 3-colorableness for the planar graphs I,
Prace Nauk. Inst. Mat. Fiz. Teoret. PWr. 6 (1972), 37–40.
[10] L. Lovász, Combinatorial Problems and Exercises, 2nd edition, North–Holland, 1993.
[11] A. Shen, ed., Mathematical Entertainments, Math. Intelligenser 19 (1997), 48–49.
[12] A. Shen, ed., Mathematical Entertainments, Math. Intelligenser 20 (1998), 30–31.
[13] D. Singmaster, Problem E 2897 Amer. Math. Monthly 88 (1981), 537; solved by J. W. Grossman
and by E. M. Reingold, Amer. Math. Monthly 90 (1983), 287–288.
[14] R. Steinberg, The state of the three color problem, in: J. Gimbel, J. W. Kennedy and L. V.
Quintas (eds.), Quo Vadis, Graph Theory, Annals of Discrete Math. 55 (1993), 211–248.
[15] L. Stockmeyer, Planar 3-colorability is polynomial complete. ACM SIGACT News 5 (1973),
19–25.
[16] W. T. Tutte, On the imbedding of linear graphs in surfaces, Proc. London Math. Soc. 51 (1949),
199–203.
[17] W. T. Tutte, A contribution on the theory of chromatic polynomials, Canad. J. Math. 6 (1954),
80–91.