#### by Robin Thomas

Every planar map of connected countries can be colored using four colors in such a way that countries with a common boundary segment (not just a point) receive different colors. It is amazing that such a simply stated result resisted proof for one and a quarter centuries, and even today it is not yet fully understood. In this article I concentrate on recent developments: equivalent formulations, a new proof, and progress on some generalizations.

#### Brief history

The Four-Color Problem dates back to 1852 when
Francis Guthrie,
while
trying to color the map of the counties of England, noticed that four
colors sufficed. He asked his brother
Frederick
if it was true that
*any* map can be colored using four colors in such a way that adjacent
regions (i.e., those sharing a common boundary segment, not just a
point) receive different colors. Frederick Guthrie then communicated
the conjecture to
DeMorgan.
The first printed reference is by
Cayley
in 1878.

A year later the first “proof” by Kempe appeared; its incorrectness was pointed out by Heawood eleven years later. Another failed proof was published by Tait in 1880; a gap in the argument was pointed out by Petersen in 1891. Both failed proofs did have some value, though. Kempe proved the five-color theorem (Theorem 2 below) and discovered what became known as Kempe chains, and Tait found an equivalent formulation of the Four-Color Theorem in terms of edge 3-coloring, stated here as Theorem 3.

The next major contribution came in 1913 from G. D. Birkhoff, whose work allowed Franklin to prove in 1922 that the Four-Color Conjecture is true for maps with at most 25 regions. The same method was used by other mathematicians to make progress on the Four-Color Problem. Important here is the work by Heesch, who developed the two main ingredients needed for the ultimate proof — “reducibility” and “discharging”. While the concept of reducibility was studied by other researchers as well, the idea of discharging, crucial for the unavoidability part of the proof, is due to Heesch, and he also conjectured that a suitable development of this method would solve the Four-Color Problem. This was confirmed by Appel and Haken (abbreviated A&H) when they published their proof of the Four-Color Theorem in two 1977 papers, the second one joint with Koch. An expanded version of the proof was later reprinted in [1].

Let me state the result precisely. Rather than trying to define maps, countries, and their boundaries, it is easier to restate Guthrie’s 1852 conjecture using planar duality. For each country we select a capital (an arbitrary point inside that country) and join the capitals of every pair of neighboring countries. Thus we arrive at the notion of a plane graph, which is formally defined as follows.

A *graph* __\( G \)__ consists of a finite set __\( V (G) \)__, the set of *vertices* of
__\( G \)__, a finite set __\( E(G) \)__, the set of *edges* of __\( G \)__, and an incidence
relation between vertices and edges such that every edge is incident
with two distinct vertices, called its *ends*. (Thus I permit parallel
edges, but do not allow edges that are loops.) A *plane graph* is a
graph __\( G \)__ such that __\( V (G) \)__ is a subset of the plane, each edge __\( e \)__ of
__\( G \)__ with ends __\( u \)__ and __\( v \)__ is a polygonal arc in the plane with
end-points __\( u \)__ and __\( v \)__ and otherwise disjoint from __\( V (G) \)__, and every
two distinct edges are disjoint except possibly for their ends. A
*region* of __\( G \)__ is an arcwise-connected component of the complement of
__\( G \)__. A graph is *planar* if it is isomorphic to a plane graph.
(Equivalently, one can replace “polygonal” in the above definition by
“continuous image of __\( [0, 1] \)__” or, by Fáry’s theorem, by “straight
line segment”, and the class of planar graphs remains the same.) For
an integer __\( k \)__, a __\( k \)__-*coloring* of a graph __\( G \)__ is a mapping
__\[ \phi : V (G) \to
\{1, \dots, k\} \]__
such that __\( \phi(u) = \phi(v) \)__ for every edge of __\( G \)__ with ends __\( u \)__
and __\( v \)__. An example of a plane graph with a 4-coloring is given in
the left half of Figure 1 below. The Four-Color Theorem (abbreviated 4CT)
now can be stated as follows.

While Theorem 1 presented a major challenge for several generations of mathematicians, the corresponding statement for five colors is fairly easy to see. Let us state and prove that result now.

*Proof*.
Let __\( G \)__ be a plane graph, and let __\( R \)__ be the number of
regions of __\( G \)__. We proceed by induction on __\( |V (G)| \)__. We may assume
that __\( G \)__ is connected, has no parallel edges, and has at least three
vertices. By Euler’s formula
__\[ |V (G)| + R = |E(G)| + 2 .\]__
Since every
edge is incident with at most two regions and the boundary of every
region has length at least 3, we have __\( 2|E(G)| \geq 3R \)__. Thus
__\[ |E(G)| \leq 3|V (G)| - 6 .\]__
The *degree* of a vertex is the number of
edges incident with it. Since the sum of the degrees of all vertices
of a graph equals twice the number of edges, we see that __\( G \)__ has a
vertex __\( v \)__ of degree at most 5.

If __\( v \)__ has degree at most 4, we consider the graph __\( G\backslash v \)__
obtained from __\( G \)__ by deleting __\( v \)__ (and all edges incident with __\( v \)__).
The graph __\( G\backslash v \)__ has a 5-coloring by the induction
hypothesis, and since __\( v \)__ is adjacent to at most four vertices, this
5-coloring may be extended to a 5-coloring of __\( G \)__. Thus we may assume
that __\( v \)__ has degree 5. I claim that __\( J \)__, the subgraph of __\( G \)__
induced by the neighbors of __\( v \)__, has two distinct vertices that are
not adjacent to each other. Indeed, otherwise __\( J \)__ has
__\( \bigl(\begin{smallmatrix}5\\2\end{smallmatrix}\bigr) = 10 \)__ edges, and yet
__\[ |E(J)| \leq 3|V (J)| - 6 =
9 \]__
by the inequality of the previous paragraph. Thus there exist two
distinct neighbors __\( v_1 \)__ and __\( v_2 \)__ of __\( v \)__ that are not adjacent to
each other in __\( J \)__, and hence in __\( G \)__. Let __\( H \)__ be the graph obtained
from __\( G\backslash v \)__ by identifying __\( v_1 \)__ and __\( v_2 \)__; it is clear that
__\( H \)__ is a graph (it has no loops) and that it may be regarded as a
plane graph. By the induction hypothesis the graph __\( H \)__ has a
5-coloring. This 5-coloring gives rise to a 5-coloring __\( \phi \)__ of
__\( G\backslash v \)__ such that __\( \phi (v_1 ) = \phi (v_2) \)__. Thus the
neighbors of __\( v \)__ are colored using at most four colors, and hence __\( \phi \)__ can
be extended to a 5-coloring of __\( G \)__, as desired. □

For future reference it will be useful to sketch another proof of
Theorem 2. The initial part proceeds in the same manner until we reach
the one and only nontrivial step, namely, when we have a vertex __\( v \)__ of
degree 5 and a 5-coloring __\( \phi \)__ of __\( G\backslash v \)__, giving the
neighbors of __\( v \)__ distinct colors. Let the neighbors of __\( v \)__ be __\( v_1,
v_2, \dots, v_5 \)__, listed in the order in which they appear around
__\( v \)__; we may assume that __\( \phi (v_i ) = i \)__. Let __\( J_{13} \)__ be the subgraph
of __\( G\backslash v \)__ induced by vertices __\( u \)__ with __\( \phi (u) \in \{1,
3\} \)__. Let __\( \phi^{\prime} \)__ be the 5-coloring of __\( G\backslash v \)__ obtained from
__\( \phi \)__ by swapping the colors 1 and 3 on the component of __\( J_{13} \)__
containing __\( v_1 \)__. If __\( v_3 \)__ does not belong to this component, then
__\( \phi^{\prime} \)__ can be extended to a coloring of __\( G \)__ by setting __\( \phi^{\prime} (v) = 1 \)__.
We may therefore assume that __\( v_3 \)__ belongs to said component and hence
there exists a path __\( P_{13} \)__ in __\( G\backslash v \)__ with ends __\( v_1 \)__ and
__\( v_3 \)__ such that __\( \phi (u) \in \{1, 3\} \)__ for every vertex __\( u \)__ of
__\( P_{13} \)__. Now let __\( J_{24} \)__ be defined analogously, and by arguing in
the same manner we conclude that we may assume that there exists a
path __\( P_{24} \)__ in __\( G\backslash v \)__ with ends __\( v_2 \)__ and __\( v_4 \)__ such that
__\( \phi(u) \in \{2, 4\} \)__ for every vertex __\( u \)__ of __\( P_{24} \)__. Thus __\( P_{13} \)__ and __\( P_{24} \)__
are vertex-disjoint, contrary to the Jordan curve theorem.

#### Equivalent formulations

Another attractive feature of the 4CT, apart from the simplicity of its formulation, is that it has many equivalent formulations using the languages of several different branches of mathematics. Indeed, in a 1993 article Kauffman and Saleur write: “While it has sometimes been said that the four-color problem is an isolated problem in mathematics, we have found that just the opposite is the case. The four-color problem and the generalization discussed here is central to the intersection of algebra, topology, and statistical mechanics.”

Saaty
[e1]
presents 29 equivalent formulations of the 4CT. In
this article let me repeat the most classical reformulation and then
mention three new ones. A graph is *cubic* if every vertex has degree
3, that is, is incident with precisely three edges. An *edge
3-coloring* of a graph __\( G \)__ is a mapping
__\[ \psi : E(G) \to \{1, 2, 3\} \]__
such that __\( \psi (e) \neq \psi (f ) \)__ for every two edges __\( e \)__ and __\( f \)__ of
__\( G \)__ that have a common end. Examples of a cubic graph and an edge
3-coloring are given in the right half of Figure 1. A *cut-edge* of a
graph __\( G \)__ is an edge __\( e \)__ such that the graph __\( G\backslash e \)__ obtained
from __\( G \)__ by deleting __\( e \)__ has more connected components than __\( G \)__. It
is easy to see that if a cubic graph has an edge 3-coloring, then
it has no cut-edge. Tait (see also
[e2],
or
[e5])
showed in 1880 that the 4CT is equivalent to the following.

In this article let me repeat the most classical reformulation and
then mention three new ones. A graph is cubic if every vertex has
degree 3, that is, is incident with precisely three edges. An edge
3-coloring of a graph __\( G \)__ is a mapping
__\[ \psi : E(G) \to \{1, 2, 3\} \]__
such that __\( \psi
(e) =\psi (f ) \)__ for every two edges __\( e \)__ and __\( f \)__ of __\( G \)__ that have a common end.
Examples of a cubic graph and an edge 3-coloring are given in the
right half of Figure 1. A cut-edge of a graph __\( G \)__ is an edge __\( e \)__ such
that the graph __\( G\backslash e \)__ obtained from __\( G \)__ by deleting __\( e \)__ has more connected
components than __\( G \)__. It is easy to see that if a cubic graph has an
edge 3-coloring, then it has no cut-edge. Tait (see also
[e2]
or
[e5])
showed in 1880 that the 4CT is equivalent to the following.

The equivalence of Theorems 1 and 3 is not hard to see and can be
found in most texts on graph theory. To illustrate where the
equivalence comes from, let us see that Theorem 1 implies Theorem 3.
Let __\( G \)__ be a cubic plane graph with no cut-edge; we may assume that
__\( G \)__ is connected. The 4CT implies that the regions of __\( G \)__ can be
colored using four colors in such a way that the two regions incident
with the same edge receive different colors (those two regions are
distinct, because __\( G \)__ has no cut-edge). Let us use the colors __\( (0,
0) \)__, __\( (1, 0) \)__, __\( (0, 1) \)__, and __\( (1, 1) \)__ instead of __\( 1, 2, 3, 4 \)__. Given
such a 4-coloring, give an edge of __\( G \)__ the color that is the sum of
the colors of the two regions incident with it, the sum taken in
__\( \mathbb{Z}_2\times \mathbb{Z}_2 \)__. Since the two regions incident
with an edge are distinct, only the colors __\( (1, 0) \)__, __\( (0, 1) \)__, and
__\( (1, 1) \)__ will be used to color the edges of __\( G \)__, giving rise to an
edge 3-coloring of __\( G \)__, as desired.

Let me now describe three striking reformulations of the 4CT. The
first is similar but deeper than a result found by
Whitney
and discussed in
[e1].
Let __\( \times \)__ denote the vector cross product in __\( \mathbb{R}^3 \)__. The
vector cross product is not associative, and hence the expression
__\[
v_1 \times v_2 \times \cdots \times v_k
\]__
is not well defined, unless __\( k \leq 2 \)__. In order to make
the expression well defined, one needs to insert
parentheses to indicate the order of evaluation. By
an *association* we mean an expression obtained by
inserting __\( k - 2 \)__ pairs of parentheses so that the
order of evaluation is determined. Thus
__\[
(v_1 \times v_2 ) \times (v_3 \times v_4 ) \quad \text{and} \quad ((v_1 \times v_2 ) \times v_3 ) \times v_4
\]__
are two examples of associations. One can ask
whether
given
two
associations
of
__\[ v_1 \times v_2 \times \cdots \times v_k \]__
there exists some choice of
vectors such that the evaluations of the two
associations are equal. This is easy to do by choosing
__\( v_1 = v_2 = \cdots = v_k \)__. But how about making the two
evaluations equal and *nonzero*? Kauffman
[e3]
has shown the following.

__\( \mathbf{i}, \mathbf{j}, \mathbf{k} \)__be the usual unit vector basis of

__\( \mathbb{R}^3 \)__. If two associations of

__\[ v_1 \times v_2 \times \dots \times v_k \]__are given, there exists an assignment of

__\( \mathbf{i}, \mathbf{j}, \mathbf{k} \)__to

__\( v_1, v_2, \dots, v_k \)__such that the evaluations of the two associations are equal and nonzero.

At this point interested readers might try to prove Theorem 4 before reading further. After all, it is only a statement about the vector cross product in a 3-dimensional space, and so it cannot be too hard. Or can it? Kauffman [e3] has also shown:

Let me clarify that Kauffman proves Theorem 4 by reducing it to the Four-Color Theorem, and so despite Theorem 5 he did not obtain a new proof of the 4CT.

Where does Theorem 5 come from? To understand it, we should think of
an association as a rooted tree in the natural sense. Given two
associations __\( A_1 \)__ and __\( A_2 \)__ of
__\[ v_1 \times v_2 \times \cdots\times v_k ,\]__
let us grow the corresponding trees __\( T_1 \)__ and __\( T_2 \)__ vertically in
opposite directions, as in the left half of Figure 2. Let us join the
roots of __\( T_1 \)__ and __\( T_2 \)__ by an edge, identify the leaves corresponding
to the same variable, and suppress the resulting vertices of degree
2, forming a cubic plane graph __\( H \)__. This process is illustrated in
the right half of Figure 2. It is easy to see that __\( H \)__ has no cut-edge
and hence has an edge 3-coloring by the 4CT. Let us use the colors
__\( \mathbf{i}, \mathbf{j}, \mathbf{k} \)__ instead of 1, 2, 3. Noticing that
each variable __\( v_i \)__ corresponds to an edge of __\( H \)__, we see that this
edge 3-coloring gives an assignment of __\( \mathbf{i}, \mathbf{j},
\mathbf{k} \)__ to the variables __\( v_1, v_2, \dots, v_k \)__ and it follows
from the construction that for this assignment the absolute values of
the evaluations of __\( A_1 \)__ and __\( A_2 \)__ are equal to the color assigned to
the edge of __\( H \)__ that joins the roots of __\( T_1 \)__ and __\( T_2 \)__. Thus we have
shown that the 4CT gives an assignment such that the corresponding
evaluations are nonzero and either they are equal or one equals the
negative of the other. It can in fact be shown that the evaluations
are indeed equal, but we shall not prove that here.

This explains why the 4CT implies Theorem 4. To prove the converse,
one must show that it suffices to prove Theorem 3 for cubic graphs __\( H \)__
that arise in the above manner. That follows from a deep theorem of
Whitney on hamiltonian circuits in planar triangulations.

For the next reformulation let __\( L \)__ denote the Lie algebra __\( \operatorname{sl}(N) \)__, that
is, the vector space of all real __\( N \times N \)__ matrices with trace zero and
with the product __\( [A, B] \)__ defined by
__\[ [A, B] = AB - BA .\]__
Let __\( \{A_i\} \)__ be a
vector space basis of __\( L \)__. The *metric tensor* __\( t_{ij} \)__ is defined by
__\( t_{ij} = \operatorname{tr} (A_i, A_j) \)__,
where __\( \operatorname{tr} \)__ denotes the trace of a matrix. Let __\( t^{ij} \)__ denote the
inverse of the metric tensor, and let __\( f_{ijk} \)__ be the *structure constants*
of __\( L \)__, defined by
__\[ f_{ijk} = \operatorname{tr} (A_i [A_j, A_k ]) .\]__
Now let __\( G \)__ be a cubic
graph, and let us choose, for every vertex __\( v \in V (G) \)__, a cyclic
permutation of the edges of __\( G \)__ incident with __\( v \)__. Our objective is to
define an invariant __\( W_L (G) \)__. To this end, let us break every edge of
__\( G \)__ into two half-edges and label all the half-edges by indices from
__\( \{1, 2, \dots \)__, __\( \dim L\} \)__. With each such labeling __\( \lambda \)__ we associate the
product
__\[
\pi(\lambda) = \prod_{v\in V(G)} fv \prod_{e\in E(G)}t^e,
\]__
where __\( t^e = t^{ij} \)__ if the two half-edges of __\( e \)__ have labels __\( i \)__ and
__\( j \)__ (notice that __\( t^{ij} = t^{ji} \)__) and __\( f_v = f_{ijk} \)__ if the three
half-edges incident with __\( v \)__ have labels __\( i, j, k \)__ and occur around
__\( v \)__ in the cyclic order listed (notice that __\( f_{ijk} = f_{jki} =
f_{kij} \)__). Finally, we define __\( W_L (G) \)__ as the absolute value of the sum
of __\( \pi (\lambda) \)__ taken over all labelings __\( \lambda \)__ of the half-edges of __\( G \)__ by
elements of __\( \{1, 2, \dots \)__, __\( \dim L\} \)__. It follows that __\( W_L (G) \)__ does not
depend on the choice of the cyclic permutations. It can also be shown
that __\( W_L (G) \)__ does not depend on the choice of basis, but for our
purposes it suffices to stick to one fixed basis.
Further, it can be shown that __\( W_L (G) \)__ is a polynomial
in __\( N \)__ of degree at most __\( k = \frac{1}{2} |V (G)| + 2 \)__, and so we
can define __\( W^{\operatorname{top}}_L (G) \)__ to be the coefficient of __\( N^k \)__ in
__\( W_L(G) \)__. The next result, due to
Bar-Natan
[e8],
is best introduced by a quote from his paper: “For
us who grew up thinking that all there is to learn
about __\( \operatorname{sl}(N) \)__ is already in __\( \operatorname{sl}(2) \)__, this is not a big
surprise.”

__\( G \)__,

__\( W_{\operatorname{sl}(2)} (G) = 0 \)__implies

__\( W^{\operatorname{top}}_{\operatorname{sl}(N)} (G) = 0 \)__.

However, the following theorem of Bar-Natan *is*
surprising, regardless of what one grew up thinking about the relationship of __\( \operatorname{sl}(2) \)__ and __\( \operatorname{sl}(N) \)__.

Like Theorem 4, Theorem 6 is deduced from the Four-Color Theorem, and hence Theorem 7 does not yield a new proof of the 4CT.

There is an easy hint as to why Theorem 7 holds.
Penrose has shown that __\( W_{\operatorname{sl}(2)} (G) \)__ is a nonzero
constant multiple of the number of edge 3-colorings
of __\( G \)__. Bar-Natan has shown that if __\( G \)__ is a connected cubic graph,
then __\( W^{\operatorname{top}}_{\operatorname{sl}(N)} (G) \)__ is 0 if __\( G \)__ has a
cut-edge and is equal to the number of embeddings
of __\( G \)__ in the sphere otherwise. The two results
combined with Theorem 3 immediately establish
Theorems 6 and 7. The details may be found in
[e8].

The last reformulation, in terms of divisibility, is due to Matiyasevich [e9].

__\( A_k \)__,

__\( B_k \)__,

__\( C_k \)__, and

__\( D_k \)__

__\( (k = 1, 2, \dots, 986) \)__of 21 variables such that the Four-Color Theorem is equivalent to the statement that for every two positive integers

__\( n, m \)__there exist nonnegative integers

__\( c_1, c_2, \dots, c_{20} \)__such that

__\[ \prod^{986}_{k=1} \begin{pmatrix} A_k (m, c_1, c_2, \dots, c_{20}) + 7^n B_k (m, c_1, c_2, \dots, c_{20})\\ C_k (m, c_1, c_2, \dots, c_{20}) + 7^n D_k (m, c_1, c_2, \dots, c_{20}) \end{pmatrix} \]__is not divisible by 7.

In fact, Matiyasevich found the functions __\( A_k \)__, __\( B_k \)__,
__\( C_k \)__, and __\( D_k \)__ explicitly, and he conjectures that a
more general statement holds.

Let us try to understand where this theorem
comes from. Let __\( \mathbb{N} \)__ denote the set of nonnegative
integers. For a positive integer __\( n \)__ let __\( S_n \)__ denote the
infinite graph with vertex-set __\( \mathbb{N} \)__ in which vertices
__\( i \)__ and __\( j \)__ are adjacent if __\( |i - j| = 1 \)__ or __\( |i - j| = n \)__. A
*discrete map* is a pair __\( (n, \mu) \)__, where __\( n \in \mathbb{N} \)__ and
__\( \mu : \mathbb{N} \to \mathbb{N} \)__ is a mapping such that __\( \mu(i) = 0 \)__ for all
but finitely many __\( i \in \mathbb{N} \)__. A discrete map __\( (n, \mu) \)__ gives
rise to a graph as follows. Let __\( H^{\prime} \)__ be the subgraph
of __\( S_n \)__ induced by all vertices __\( i \)__ with __\( \mu(i) \neq 0 \)__, and
let __\( H \)__ be obtained from __\( H^{\prime} \)__ by contracting all edges
with ends __\( i, j , \)__ where __\( \mu(i) = \mu (j) \)__. Then __\( H \)__ is indeed
a graph (it is loopless), and __\( \mu \)__ is a coloring of __\( H \)__.
We say that two discrete maps __\( (n, \mu) \)__ and __\( (n^{\prime}, \mu^{\prime}) \)__
are *equivalent* if

__\( n = n^{\prime} \)__,__\( \mu(i) = 0 \)__if and only if__\( \mu^{\prime}(i) = 0 \)__,__\( \mu (i) = \mu (i + 1) \)__if and only if__\( \mu^{\prime}(i) = \mu^{\prime}(i + 1) \)__, and__\( \mu (i) = \mu(i + n) \)__if and only if__\( \mu^{\prime} (i) = \mu^{\prime} (i + n) \)__.

It is not too difficult to show that every planar
graph arises as the planar graph __\( H \)__ above for some
discrete map and hence the 4CT is equivalent to

__\( (n, \mu) \)__there exists an equivalent discrete map

__\( (n, \lambda \)__) such that

__\( \lambda (i) \in \{0, 1, 2, 3, 4\} \)__for all

__\( i \in \mathbb{N} \)__.

By Theorem 2 we can in the above theorem
confine ourselves to discrete maps __\( (n, \mu) \)__ such that
__\( \mu (i) \in \{0, 1, 2, 3, 4,5\} \)__ for all __\( i \in \mathbb{N} \)__.
Each such function __\( \mu \)__ can
be encoded as an integer
__\[ m =\sum^{\infty}_{i=0} \mu (i)7^i .\]__
Thus the phrase “for every two
integers __\( n, m \)__” in Theorem 8 plays the role of “for
every plane graph”. Similarly, the function __\( \lambda \)__ can
be encoded as an integer, but we prefer to encode
it using the 20 integers __\( c_1, c_2, \dots, c_{20} \)__ defined
for __\( i = 0, 1, \dots, 4 \)__ and __\( j = 1, 2, 3, 4 \)__ by
__\[
c_{4i+j} =\sum (7^k : \mu(k) = i + 1, \lambda(k) = j).
\]__
Now there are conditions the integers
__\( c_1, c_2,\dots, c_{20} \)__ have to satisfy in order to represent
a valid discrete map __\( (n, \lambda) \)__ as in Theorem 9, but
each such condition can be expressed in the form
“7 does not divide __\( \bigl(\begin{smallmatrix} A+7^nB\\C+7^n
D\end{smallmatrix}\bigr) \)__”,
where __\( A, B, C, D \)__ are
linear functions of __\( m, c_1, c_2, \dots, c_{20} \)__. The reader
may find more details in
[e9].

#### An outline

The work of Appel and Haken undoubtedly represents a major breakthrough in mathematics, but, unfortunately, there remains some skepticism regarding the validity of their proof. To illustrate the nature of those concerns, let me quote from a 1986 article by Appel and Haken themselves: “This leaves the reader to face 50 pages containing text and diagrams, 85 pages filled with almost 2500 additional diagrams, and 400 microfiche pages that contain further diagrams and thousands of individual verifications of claims made in the 24 lemmas in the main sections of text. In addition, the reader is told that certain facts have been verified with the use of about 1200 hours of computer time and would be extremely time-consuming to verify by hand. The papers are somewhat intimidating due to their style and length and few mathematicians have read them in any detail.”

A discussion of errors, their correction, and other potential problems may be found in the above article, in [1], and in F. Bernhart’s review of [1]. For the purpose of this survey, let me telescope the difficulties with the A&H proof into two points:

- part of the proof uses a computer and cannot be verified by hand, and
- even the part that is supposedly hand-checkable has not, as far as I know, been independently verified in its entirety.

To my knowledge, the most comprehensive effort to verify the A&H proof was undertaken by Schmidt. According to [1], during the one-year limitation imposed on his master’s thesis Schmidt was able to verify about 40 percent of part I of the A&H proof.

Neil Robertson, Daniel P. Sanders, Paul Seymour, and I tried to verify the Appel–Haken proof, but soon gave up and decided that it would be more profitable to work out our own proof. So we did and came up with the proof that is outlined below. We were not able to eliminate reason (1), but we managed to make progress toward (2).

The basic idea of our proof is the same as Appel and Haken’s. We
exhibit a set of 633 “configurations” and prove each of them is
“reducible”. This is a technical concept that implies that no
configuration with this property can “appear” in a minimal
counterexample to the Four-Color Theorem. It can also be used in an
algorithm, for if a reducible configuration appears in a sufficiently
connected planar graph __\( G \)__, then one can construct in constant time a
smaller planar graph __\( G^{\prime} \)__ such that any 4-coloring of __\( G^{\prime} \)__ can be
converted to a 4-coloring of __\( G \)__ in linear time.

Birkhoff showed in 1913 that every minimal counterexample to the Four-Color Theorem is an “internally 6-connected” triangulation. In the second part of the proof we prove that at least one of our 633 configurations appears in every internally 6-connected planar triangulation (not necessarily a minimal counterexample to the 4CT). This is called proving unavoidability and uses the “discharging method” first suggested by Heesch. Here our method differs from that of Appel and Haken.

The main aspects of our proof are as follows. We confirm a conjecture of Heesch that in proving unavoidability a reducible configuration can be found in the second neighborhood of an “over-charged” vertex; this is how we avoid “immersion” problems that were a major source of complication for Appel and Haken. Our unavoidable set has size 633 as opposed to the 1,476-member set of Appel and Haken; our discharging method uses only 32 discharging rules instead of the 487 of Appel and Haken; and we obtain a quadratic algorithm to 4-color planar graphs, an improvement over the quartic algorithm of Appel and Haken. Our proof, including the computer part, has been independently verified, and the ideas have been and are being used to prove more general results. Finally, the main steps of our proof are easier to present, as I will attempt to demonstrate below.

Before I turn to a more detailed discussion of configurations, reducibility, and discharging, let me say a few words about the use of computers in our proof. The theoretical part is completely described in [e6], but it relies on two results that are stated as having been proven by a computer. The rest of [e6] consists of traditional (computer-free) mathematical arguments. There is nothing extraordinary about the theoretical arguments, and so the main burden of verification lies in those two computer proofs. How is one supposed to be convinced of their validity? There are basically two ways. The reader can either write his or her own computer programs to check those results (they are easily seen to be finite problems), or he or she can download our programs along with their supporting documentation and verify that those programs do what we claim they do.

The reducibility part is easier to believe, because we are doing almost the same thing as many authors before us (including Appel and Haken) have done, and so it is possible to compare certain numerical invariants obtained during the computation to gain faith in the results. This is not possible in the unavoidability part, because our approach to it is new. To facilitate checking, we have written this part of the computer proof in a formal language so that it will be machine verifiable. Every line of the proof can be read and checked by a human, and so can (at least theoretically) the whole argument. However, the entire argument occupies about 13,000 lines, and each line takes some thought to verify. Therefore, verifying all of this without a computer would require an amount of persistence and determination my coauthors and I do not possess. The computer data, programs, and documentation are available by anonymous ftp1 and can also be conveniently accessed on the World Wide Web.2

Two of my students independently verified the computer work. Tom Fowler verified the reducibility part (and in fact extended it to obtain a more general result — see later), and Christopher Carl Heckman wrote an independent version of the unavoidability part using a different programming language. Bojan Mohar also informed us that his student Gašper Fijavž wrote independent programs and was able to confirm both parts of the computer proof. The computer verification can be carried out in a matter of several hours on standard commercially available equipment.

I should mention that both our programs use only integer arithmetic, and so we need not be concerned with round-off errors and similar dangers of floating point arithmetic. However, an argument can be made that our “proof” is not a proof in the traditional sense, because it contains steps that most likely can never be verified by humans. In particular, we have not proven the correctness of the compiler on which we compiled our programs, nor have we proven the infallibility of the hardware on which we ran our programs. These have to be taken on faith and are conceivably a source of error. However, from a practical point of view, the chance of a computer error that appears consistently in exactly the same way on all runs of our programs on all the compilers under all the operating systems that our programs run on is infinitesimally small compared to the likelihood of a human error during the same amount of case-checking. Apart from this hypothetical possibility of a computer consistently giving an incorrect answer, the rest of our proof, including the programs, can be checked in the same way as traditional mathematical proofs. My coauthors and I concede, however, that checking a computer program is much more difficult than verifying a mathematical proof of the same length.

#### Configurations

First we need a result of Birkhoff about connectivity of minimal
counterexamples. Let __\( G \)__ be a plane graph. A *triangle* is a region of
__\( G \)__ bounded by precisely three edges of __\( G \)__. A plane graph __\( G \)__ is a
*triangulation* if every region of __\( G \)__ (including the unbounded region)
is a triangle. See Figure 3 for an example. A graph __\( G \)__ is *internally
6-connected* if for every set __\( X \)__ of at most five vertices, either the
graph __\( G\backslash X \)__ obtained from __\( G \)__ by deleting __\( X \)__ is
connected, or __\( |X| = 5 \)__ and __\( G\backslash X \)__ has exactly two connected
components, one of which consists of a single vertex. Thus every
vertex of an internally 6-connected graph has degree at least 5.
For example, the triangulation in Figure 3 is internally 6-connected.
Let me formally state the result of Birkhoff mentioned earlier. A
proof can be obtained by pushing the arguments presented in the two
proofs of Theorem 2.

Next we need to introduce the concept of a configuration, which is
central to the rest of the proof. Configurations are technical devices
that permit us to capture the structure of a small part of a larger
triangulation. A graph __\( G \)__ is an *induced subgraph* of a graph __\( T \)__ if
__\( G \)__ is a subgraph of __\( T \)__ and every edge of __\( T \)__ with both ends in __\( V
(G) \)__ belongs to __\( G \)__. If __\( (G, \gamma) \)__ is a configuration, one should
think of __\( G \)__ as an induced subgraph of an internally 6-connected
triangulation __\( T \)__, with __\( \gamma(v) \)__ being the degree of __\( v \)__ in __\( T \)__.
This notion can be traced back to Birkhoff’s 1913 paper and has been
used in various forms by many researchers since then. Here is the
formal definition of the version that we use.

A *near-triangulation* is a nonnull connected
plane graph with one region designated as *special*
such that every region, except possibly the special
region, is a triangle. A *configuration* __\( K \)__ is a pair
__\( (G, \gamma) \)__, where __\( G \)__ is a near-triangulation and __\( \gamma \)__ is a
mapping from __\( V(G) \)__ to the integers with the following properties:

- for every vertex
__\( v \)__of__\( G \)__, if__\( v \)__is not incident with the special region of__\( G \)__, then__\( \gamma(v) \)__equals__\( \deg(v) \)__, the degree of__\( v \)__, and otherwise__\( \gamma(v) > \deg(v) \)__, and in either case__\( \gamma(v) \geq 5 \)__; - for every vertex
__\( v \)__of__\( G \)__,__\( G\backslash v \)__has at most two components, and if there are two, then the degree of__\( v \)__in__\( G \)__is__\( \gamma (v) - 2 \)__; __\( K \)__has ring-size at least 2, where the*ring-size*of__\( K \)__is defined to be__\[ \sum(\gamma(v) - \deg(v) - 1) ,\]__summed over all vertices__\( v \)__incident with the special region of__\( G \)__such that__\( G\backslash v \)__is connected.

The significance of condition (1) will become clearer from the definition of “appears” below; conditions (2) and (3) are needed for the definition of the “free completion”, discussed in the next section.

When drawing pictures of configurations, one
possibility is to draw the underlying graph and
write the value of __\( \gamma \)__ next to each vertex. There is
a more convenient way, introduced by Heesch.
The special region is the unbounded region, and
the shapes of vertices indicate the value of __\( \gamma(v) \)__
as follows: A solid black circle means __\( \gamma(v) = 5 \)__, a
dot (or what appears in the picture as no symbol
at all) means __\( \gamma(v) = 6 \)__, a hollow circle means
__\( \gamma(v) = 7 \)__, a hollow square means __\( \gamma(v) = 8 \)__,
a triangle means __\( \gamma(v) = 9 \)__, and a pentagon means
__\( \gamma(v) = 10 \)__. In Figure 4, 17 of our
633 reducible configurations are displayed using the
indicated convention. The whole set can be found in
[e6]
and can be viewed electronically.3

Isomorphism of configurations is defined in
the natural way. Any configuration isomorphic to
one of the 633 configurations exhibited in
[e6]
is called a *good* configuration. Let __\( T \)__ be a triangulation. A configuration
__\( (G, \gamma) \)__ *appears* in __\( T \)__ if __\( G \)__ is an induced subgraph of __\( T \)__,
every region of __\( G \)__ except possibly the special region is a region of
__\( T \)__, and __\( \gamma(v) \)__ equals the degree of __\( v \)__ in __\( T \)__ for every vertex
__\( v \)__ of __\( G \)__. See Figure 3 for an example of a configuration isomorphic
to the first configuration in Figure 4 appearing in an internally
6-connected triangulation. We prove the following two statements.

__\( T \)__is a minimal counterexample to the Four-Color Theorem, then no good configuration appears in

__\( T \)__.

__\( T \)__, some good configuration appears in

__\( T \)__.

For example, the good configuration in the upper left corner of Figure 4 appears in the center of Figure 3.

From Theorems 10, 11, and 12 it follows that no minimal counterexample exists, and so the 4CT is true. I will discuss the proofs of the latter two theorems in the next two sections.

#### Reducibility

Reducibility is a technique for proving statements such as Theorem 11. Qualitatively it can be described by saying that it is obtained by pushing to the limit the arguments used in the two proofs of Theorem 2. It was developed from Kempe’s failed attempt at proving the 4CT by Birkhoff, Bernhart, Heesch, Allaire, Swart, Appel and Haken, and others.

I will explain the idea of reducibility by giving
an example; interested readers may find the precise definition in
[e6].
Let us consider the first configuration in Figure 4, and let
us call it __\( K = (G, \gamma) \)__.
Suppose for a contradiction that __\( K \)__ appears in a
minimal counterexample __\( T \)__ to the 4CT. Given that
__\( \gamma(v) \)__ is equal to the degree in __\( T \)__ of the vertex __\( v \)__ of
__\( G \)__, we can deduce what __\( T \)__ looks like in a small
“neighborhood” of __\( G \)__. In fact, since __\( T \)__ is internally
6-connected by Theorem 10, it follows that the
graph __\( S \)__ pictured in Figure 5 is isomorphic to a
subgraph of __\( T \)__, and so we may assume that __\( S \)__ is
actually a subgraph of __\( T \)__. Notice that __\( G \)__ is a subgraph
of __\( S \)__, that __\( R = S\backslash V (G) \)__ is a (simple) circuit with
vertex-set __\( \{v_1, v_2, \dots \)__, __\( v_6\} \)__, and that the length of __\( R \)__
is equal to the ring-size of __\( K \)__. We call __\( S \)__ the *free
completion* of __\( K \)__.

(Here we were lucky — for larger configurations it does not
follow that the free completion is a subgraph of __\( T \)__. However, the
most that can happen, given that __\( G \)__ is an *induced* subgraph of __\( T \)__, is
that for some distinct vertices of __\( R \)__ the corresponding vertices of __\( T \)__
are equal. On the other hand, this does not matter for the forthcoming
argument, and so for the purpose of this article let me ignore this
possibility.)

Now let us consider
__\[ T^{\prime} = T \backslash V (G) .\]__
Let __\( \mathcal{K} \)__ be the set of
all 4-colorings of __\( R \)__, and let __\( \mathcal{C}^{\prime}\subseteq \mathcal{K} \)__ be the set of all those
4-colorings of __\( R \)__ that extend to a 4-coloring of __\( T^{\prime} \)__. Since __\( T \)__ is a
minimal counterexample, __\( T^{\prime} \)__ has a 4-coloring, and hence __\( \mathcal{C}^{\prime} =
\emptyset \)__. To obtain a contradiction, let me prove that __\( \mathcal{C}^{\prime} =
\emptyset \)__. Let __\( \mathcal{C} \)__ be the set of all 4-colorings of __\( R \)__ that extend
to a 4-coloring of __\( S \)__. Notice that __\( \mathcal{C} \)__ can be computed from the
knowledge of the configuration __\( K \)__. Since __\( T \)__ is a counterexample to
the 4CT, __\( \mathcal{C}^{\prime} \subseteq \mathcal{K} - \mathcal{C} \)__ (otherwise a 4 -coloring of __\( R \)__ that
extends to both __\( S \)__ and __\( T^{\prime} \)__ extends to a 4-coloring of __\( T \)__). We need a
method that would allow us to show that a 4-coloring __\( \phi \in \mathcal{K} - \mathcal{C} \)__
does not belong to __\( \mathcal{C}^{\prime} \)__. As an example let us consider the 4-coloring
__\( \phi \)__ of __\( R \)__ defined by
__\[ (\phi(v_1 ), \phi(v_2 ), \dots, \phi(v_6)) =
(1, 2, 1, 3, 1, 2) ,\]__
where __\( v_1, v_2, \dots, v_6 \)__ are the vertices of
__\( R \)__, numbered as in Figure 5. To simplify the notation, I shall write
__\( \phi = 121312 \)__ and similarly for other colorings. Suppose for a
contradiction that __\( \phi \in \mathcal{C}^{\prime} \)__, and let __\( \kappa \)__ be a 4-coloring of
__\( T^{\prime} \)__ extending __\( \phi \)__. Let __\( T_{14} \)__ be the subgraph of __\( T^{\prime} \)__ induced by
the vertices __\( v \in V (T^{\prime}) \)__ with __\( \kappa(v) \in \{1, 4\} \)__, and let __\( L \)__
be the component of __\( T_{14} \)__ containing the vertex __\( v_1 \)__. Let __\( \kappa^{\prime} \)__
be obtained from __\( \kappa \)__ by exchanging colors 1 and 4 on vertices of
__\( L \)__, and let __\( \phi^{\prime} \)__ be the restriction of __\( \kappa^{\prime} \)__ to __\( R \)__. Thus __\( \phi^{\prime}
\in \mathcal{C}^{\prime} \)__. If __\( v_3 , v_5 \notin V (L) \)__, then __\( \phi^{\prime} = 421312 \)__, and if __\( v_3
\notin V (L) \)__, __\( v_5 \in V (L) \)__, then __\( \phi^{\prime} = 421342 \)__. In either case
__\( \phi^{\prime} \in \mathcal{C} \)__ (see Figure 6), a contradiction. Thus __\( v_3 \in V (L) \)__,
and hence there exists a path __\( P \)__ in __\( T^{\prime} \)__ with ends __\( v_1 \)__ and __\( v_3 \)__
such that __\( \kappa(v) \in \{1, 4\} \)__ for every __\( v \in V (P ) \)__. Let
__\( T_{23} \)__ be defined analogously, and let __\( J \)__ be the component of
__\( T_{23} \)__ containing __\( v_2 \)__. Since __\( V (J) \cup V (P ) = \emptyset \)__ we
deduce from the Jordan curve theorem that __\( v_4, v_6 \notin V (J) \)__. Let
__\( \kappa^{\prime\prime} \)__ be obtained from __\( \kappa \)__ by exchanging colors 2 and 3 on
vertices of __\( J \)__, and let __\( \phi^{\prime\prime} \)__ be the restriction of __\( \kappa^{\prime\prime} \)__ to __\( R \)__.
Then __\( \phi^{\prime\prime} = 131312 \)__, and hence __\( \phi^{\prime\prime} \in \mathcal{C} \)__ (see Figure 6), and yet
__\( \phi^{\prime\prime} \in \mathcal{C}^{\prime} \)__, a contradiction. Thus __\( \phi \notin \mathcal{C}^{\prime} \)__, as required. The
arguments for other colorings in __\( \mathcal{K} - \mathcal{C} \)__ proceed similarly. The order
in which colorings are handled is important here, because for some
colorings it is necessary to use the previously
established fact that other colorings in __\( \mathcal{K} - \mathcal{C} \)__ do not
belong to __\( \mathcal{C}^{\prime} \)__.

The above argument is called D-*reducibility* in the literature.
Notice the way in which we used the fact that __\( T \)__ is a minimal
counterexample — we used it to deduce that __\( T^{\prime} \)__ has a 4-coloring.
This may seem wasteful, for rather than deleting __\( G \)__, we could replace
it by a smaller graph __\( G^{\prime} \)__. Doing so yields a more powerful method,
called C-*reducibility*. In our proof of the 4CT we use a special case
of C-reducibility, where __\( G^{\prime} \)__ is obtained from __\( G \)__ by contracting at
most four edges. C-reducibility is dangerous in general, because it
requires checking that the new graph obtained by substituting __\( G^{\prime} \)__ for
__\( G \)__ is loopless, which can be rather tedious. By limiting ourselves to
graphs obtained by contracting at most four edges, we were able to
eliminate these difficulties.

D- and C-reducibility can be automated and carried out on a computer. In fact, they must be carried out on a computer, because we need to test configurations with ring-size as large as 14, in which case there are almost 200,000 colorings to be checked. At the present time there is little hope of doing this part of the proof by hand. Even writing down the proof in a formal language, as we did for the discharging part, does not seem practical because of the length of the argument.

#### Discharging

Discharging is a clever and effective use of Euler’s formula, first suggested by Heesch and later used by Appel and Haken and many others since then. In fact, discharging has become a standard tool in graph theory. In what follows I will refer to Figure 7, which some readers may find overwhelming at the first sight. I recommend focusing attention on the first row and thinking of the rest as being of secondary importance. The first row has a geometric interpretation, discussed below. Also, we will make use of Heesch’s notational convention introduced two paragraphs prior to Theorem 11.

Let __\( T \)__ be an internally 6-connected triangulation. Initially, every
vertex __\( v \)__ is assigned a *charge* of
__\[ 10(6 - \deg(v)) .\]__
It follows from
Euler’s formula that the sum of the charges of all vertices is 120;
in particular, it is positive. We now redistribute the charges
according to the following rules. Whenever __\( T \)__ has a subgraph
isomorphic to one of the graphs in Figure 7 satisfying the degree
specifications (for a vertex __\( v \)__ of one of those graphs with a minus
sign next to __\( v \)__, this means that the degree of the corresponding
vertex of __\( T \)__ is at most the value specified by the shape of __\( v \)__, and
analogously for vertices with a plus sign next to them; equality is
required for vertices with no sign next to them), a charge of 1
(2 in case of the first graph) is to be sent along the edge marked with
an arrow.

This procedure defines a new set of charges with the same total sum.
For instance, if __\( T \)__ is the triangulation depicted in Figure 3, then
only the rule corresponding to the first graph in Figure 7 applies,
and it causes a charge of 2 to be sent along each edge in either
direction. Hence the net effect of all the rules is zero, and so every
vertex ends up with a final charge of 10.

Since the total sum of the new charges is positive, there is a vertex
__\( v \)__ in __\( T \)__ whose new charge is positive. We show that a good configuration
appears in the second neighborhood of __\( v \)__ (that is, the subgraph
induced by vertices at distance at most 2 from __\( v \)__). If the degree of
__\( v \)__ is at most 6 or at least 12, then this can be seen fairly
easily by a direct argument. (See
[e6]
for details; for this argument
the configurations of Figure 4 suffice. In fact, when __\( v \)__ has degree at
most 6, this follows immediately from the geometric interpretation
of the first row of Figure 7 given at the end of this section.) For
the remaining cases, however, the proofs are much more complicated.
Since the amount of charge a vertex of __\( T \)__ receives depends only on its
second neighborhood (and not on the rest of __\( T \)__), it suffices to
examine all possible second neighborhoods of vertices of degree 7,
8, 9, 10, and 11. It is easy to see that this reduces to a finite
problem. Strictly speaking, there are infinitely many such second
neighborhoods, but for vertices of degree at least 12 the actual
degree affects neither the amount of charge nor the presence of
reducible configurations. Thus all possible second neighborhoods can
be divided into finitely many classes, where for every two second
neighborhoods in the same class, the same good configurations appear
and the central vertex has the same charge. Therefore, it suffices to
examine all these equivalence classes. As mentioned earlier,
this part of the proof has actually been written down in a formal language.

The rules corresponding to the first row in Figure 7 were derived from
an elegant method of
Mayer and have the following geometric
interpretation. Let __\( v \in V (T ) \)__ have degree 5, and assume, as we
may in the proof of Theorem 12, that no good configuration appears in
the second neighborhood of __\( v \)__. The vertex __\( v \)__ is originally assigned
a charge of 10. The rules in the first row are designed to send this
charge from __\( v \)__ to vertices of degree at least 7. Let __\( e \)__ be an
edge incident with __\( v \)__, let __\( u \)__ be the other end of __\( e \)__, and let __\( x \)__
be a common neighbor of __\( u \)__ and __\( v \)__. Since __\( T \)__ is internally
6-connected, there are exactly ten such pairs __\( (e, x) \)__. For each such
pair a charge of 1 will be sent away from __\( v \)__ into a suitable
vertex, found as follows. If the degree of __\( u \)__ is at least 7, the
unit of charge will be deposited into __\( u \)__. Otherwise, if __\( x \)__ has
degree at least 7, the unit of charge will be deposited into __\( x \)__.
Finally, if both __\( u \)__ and __\( x \)__ have degree at most 6, let
__\[ z_1 = v,
\,z_2 = u,
\,z_3, \,z_4, \dots \]__
be the neighbors of __\( x \)__ listed in the order
in which they appear around __\( x \)__. Since no good configuration appears
in the second neighborhood of __\( v \)__, one of these vertices has degree at
least 7, as is easily seen. Thus we may take the smallest
integer __\( i \geq 2 \)__ such that __\( z_i \)__ has degree at least 7, and the unit of
charge corresponding to __\( (e, x) \)__ will be deposited into __\( z_i \)__.

While this redistribution of charges seems natural, unfortunately it is not true that a reducible configuration appears in the second neighborhood of every vertex of positive charge. Therefore, we had to introduce additional rules to make small changes to this distribution to take care of second neighborhoods of vertices with positive charge in which no reducible configuration appeared. The additional rules were obtained by trial and error; there is a lot of flexibility in their choice, but they were not designed with any geometric intuition behind them.

#### Beyond the Four-Color Theorem

The new proof of the 4CT gives hope that other more general
conjectures that are known to imply the 4CT could be settled by an
appropriate adaptation of the same methods. Let me start by
discussing a result of my student
Tom Fowler
on unique colorability. A
graph __\( G \)__ is uniquely 4-colorable if it has a 4-coloring and every two
4-colorings differ only by a permutation of colors. Here is a
construction. Start with the complete graph on four vertices. Given a
plane graph __\( G \)__ constructed thus far, pick a triangle in __\( G \)__, and add
a new vertex adjacent to all vertices incident with the triangle. It
is easy to see that every graph constructed in this fashion is
uniquely 4-colorable.
Fiorini
and
Wilson
conjectured in 1977 that
every uniquely 4-colorable plane graph on at least four vertices can
be obtained this way. Fowler in his Ph.D. thesis extended our proof
of the 4CT to prove this conjecture. More precisely, he has shown

By Theorem 10 this generalizes the Four-Color Theorem, and it implies the Fiorini–Wilson conjecture by a result of Goldwasser and Zhang, who have shown that a minimal counterexample is internally 6-connected. (The proof of the latter is analogous to that of Theorem 10.)

While the 4CT becomes false very quickly once
we leave the world of planar graphs,
Tutte
noticed
that Theorem 3 remains true for a reasonably large
class of nonplanar graphs. The smallest cubic
graph with no cut-edge and no edge 3-coloring is
the famous Petersen graph depicted in Figure 8.
We say that a graph __\( G \)__ has an __\( H \)__ minor if a graph
isomorphic to __\( H \)__ can be obtained from a subgraph
of __\( G \)__ by contracting edges. Tutte conjectured the
following.

Tutte’s conjecture implies the 4CT by Theorem 3 (because the Petersen
graph is not planar, and contraction preserves planarity), but it
seems to be much stronger. However, it now appears that there is a
good chance that Tutte’s conjecture can be proven. Indeed,
Robertson,
Seymour,
and I have reduced the problem to the following two classes
of graphs. We say that a graph __\( G \)__ is *apex* if __\( G\backslash v \)__ is planar for some
vertex __\( v \)__ of __\( G \)__, and we say that a graph is *doublecross* if it can be
drawn in the plane with two crossings in such a way that the two
crossings belong to the same region (see Figure 9). Robertson,
Seymour, and I
[e7]
have shown the following.

__\( G \)__be a counterexample to Conjecture 14 with

__\( |V (G)| \)__minimum. Then

__\( G \)__is apex or doublecross.

Thus, in order to prove Conjecture 14 it suffices to prove it for apex and doublecross graphs, two classes of graphs that are “almost” planar. In fact, my recent work with Sanders suggests that it might be possible to adapt our proof of the 4CT to show that no apex graph is a counterexample to Tutte’s conjecture. There is an indication that the doublecross case will be easier, but we cannot confirm that yet.

There is a way to generalize the 4CT along the lines of (vertex) 4-coloring. Hadwiger conjectured the following.

__\( t \)__, if a graph has no

__\( K_{t+1} \)__minor, then it has a

__\( t \)__-coloring.

This is trivial for __\( t \leq 2 \)__, and for __\( t = 3 \)__ it was shown by
Hadwiger and
Dirac
(this case is also reasonably easy). However, for
every __\( t \geq 4 \)__, Hadwiger’s conjecture implies the 4CT. To see this,
take a plane graph __\( G \)__, and construct a graph __\( H \)__ by adding __\( t - 4 \)__
vertices adjacent to each other and to every vertex of __\( G \)__. Then __\( H \)__
has no __\( K_{t+1} \)__ minor (because no plane graph has a __\( K_5 \)__ minor) and
hence has a __\( t \)__-coloring by the assumed truth of Hadwiger’s
conjecture. In this __\( t \)__-coloring, vertices of __\( G \)__ are colored using at
most four colors, as required. Thus there is a rather sharp increase
in the level of difficulty of Hadwiger’s conjecture between __\( t = 3 \)__
and __\( t = 4 \)__. On the other hand,
Wagner showed in 1937 that Hadwiger’s
conjecture for __\( t = 4 \)__ is in fact equivalent to the 4CT. (Notice that
this result preceded the proof of the 4CT by four decades and, in
fact, inspired Hadwiger’s conjecture.) Recently, Robertson, Seymour,
and I were able to show that the next case is also equivalent to the
4CT
[e4].
More precisely, we managed to prove (without using the 4CT)
the following.

__\( G \)__be a counterexample to Hadwiger’s conjecture for

__\( t = 5 \)__with the minimum number of vertices. Then

__\( G \)__is apex.

By the 4CT every apex graph has a 5-coloring,
and so Hadwiger’s conjecture for __\( t = 5 \)__ follows.
The cases __\( t \geq 6 \)__ are still open.