rec.puzzles Archive

Find the flaw in this short "proof" of the four color theorem.

geometry/coloring/four.color.proof

Problem

Find the flaw in this short "proof" of the four color theorem.

As is typical in map coloring discussions, the proof will operate on
colorings of the nodes of planar graphs.  This is valid because every
colored planar map has a distinct colored planar graph which is its
dual (ie, each node in a colored planar graph represents a colored
country in the dual map, and each edge represents a shared border with
a neighboring country).

PROOF:
  1) We assume that the 4-color theorem is false (i.e., that there
     exist graphs that require at least five colors), and show that
     that assumption leads to a contradiction.  This means that the
     assumption was incorrect and that four colors are therefore
     sufficient to color any planar graph.
  2) There exists then a counterexample of smallest possible size
     (i.e. a graph with the smallest number of nodes that require 5
     colors).  Let G be such a "smallest" counterexample.
  3) Removing any node from G therefore results in a 4-colorable
     graph.
  4) Every node must therefore have valence >= 4 (ie, 4 or more
     incident edges) because if such a node existed with a valence
     less than 4, you could:
     a: remove that node (and its edges) from G,
     b: 4-color the resulting graph (via step 3), and
     c: add the node back in, coloring it differently from its <=3
        neighbors
     giving a 4-coloring of G.
  5) Every planar graph contains at least one node of valence <=5.
     (A proof of this using Euler's formula is straightforward.  I can
     supply it for anyone that cares to see it).  This fact together
     with step 4 determine that G must contain at least one node of
     valence 4 or 5.

  CASE 1: There exists a node of valence 4.  Call it v.

  6) Fix a 4-coloring of the graph G-v (read "G minus v", the subgraph
     of G with v and its edges removed).  This must be possible because
     of the definition of G.  The neighbors of v in G must all be
     different colors, say r, y, g, and b clockwise.  (If they were not
     four different colors, v could be colored using a remaining color
     to get a 4-coloring of G).
  7) Consider the largest connected subgraph of G that contains node r
     and only red and green nodes.  See figure 1.
  8) If that subgraph does not contain g, then, within that subgraph,
     recolor all red nodes green and all green nodes red.  We now have
     a 4-coloring of G-v in which no neighbor of v is red.  Therefore
     coloring v red results in a 4-coloring of G.  Contradiction.
  9) The contradiction in step 8 shows that the subgraph in step 7
     must contain g.  Therefore there exists an alternating path of
     red and green nodes that divides G-v into two parts such that y
     is in one and b is in the other.  See figure 1.
 10) Within the part containing y, recolor all yellow nodes blue and
     all blue nodes yellow.  We now have a new 4-coloring of G-v in
     which no neighbor of v is yellow.  Therefore coloring v yellow
     results in a 4-coloring of G.  Also a contradiction.  CASE 1
     leads to a contradiction either way, so it must be false.

Figure 1: node v has valence = 4

                  . . . . . .
                r             g
               /               \
              g                 r
              |                 |
              r        y        g
              |        |        |
              g        |        r
               \       |       /
                r-----(v)-----g
                       |
                       |
                       |
                       b

  CASE 2: There exists a node of valence 5.  Call it v.

 11) As in step 6, fix a 4-coloring of the graph G-v.  By the same
     reasoning as in step 6, the neighbors of v must be four different
     colors, so now there are two possible unique types of colorings of
     the neighbors of v: (clockwise) ryygb and rygyb.
 12) The proof that the ryygb case cannot exist is identical to CASE 1
     above.  See figure 2a.
 13) The final possibility to examine is where the neighbors of v are
     colored rygyb.  See figure 2b.
 14) The alternating red-green path between r and g which isolates the
     first y node from b must exist by the same reasoning as for
     CASE 1.  This means that the yellow and blue nodes in the region
     containing the first y node can swap colors, turning that y node
     blue.
 15) Likewise, the same argument can be used to show that there must
     exist a path of alternating blue-green nodes from b to g which
     isolate the second y node from r.  This means that the yellow and
     red nodes in that region can swap colors, turning that y node red.
 16) Because steps 14 and 15 allow us to recolor both y nodes to other
     colors, we can arrive at a 4-coloring of G-v in which no neighbor
     of v is yellow.  Therefore coloring v = yellow results in a
     4-coloring of G.  This proves that CASE 2 must also be false.
     Since both cases are false, G (which was any smallest
     counter-example) cannot exist proving that there can be no
     counter-examples, and that all planar graphs must be 4-colorable.

Figure 2: node v has valence = 5

           . . . . . .                   . . . . . .
         r             g               r             g
        /               \             /               \
       g                 r           g                 r
       |                 |           |                 |
       r        y   y    g           r        y        g
       |        |  /     |           |        |        |
       g        | /      r           g        |        r
        \       |/      /             \       |       /
         r-----(v)-----g               r-----(v)-----g
                |                             |\      \
                |                             | \      b
                |                             |  \      \
                b                             b   y      g
                                             /           |
                                            g            b
                                            |           /
                                            b          g
                                             . . . . .

     a:  ryygb neighbor case        b:  rygyb neighbor case

[ Editor: the "proof" is by Don Hatch and Daniel Green, "as
reconstructed from the original proof by Don Kimber"; it was posted by
Daniel Green in April 1995 with the remark that the flaw is subtle and
"cleverly hidden". ]
Show solution
The flaw is in step 16: the two recolorings of steps 14 and 15 are
each valid on its own, but they cannot both be made.  This is the same
gap as in A. B. Kempe's published "proof" of 1879, found by P. J.
Heawood in 1890 ("Map-colour theorem", Quarterly Journal of Pure and
Applied Mathematics 24).

Steps 1 to 13 are sound; they are Kempe's argument, and CASE 1 is
correct.  (In step 9 what separates y from b is the red-green chain
from r to g together with v itself; that is fine.)  In CASE 2, label
the neighbors of v clockwise r, y1, g, y2, b.

Step 14 uses the red-green chain from r to g; it separates y1 from b,
so swapping yellow and blue in the yellow-blue chain through y1 turns
y1 blue without touching b.  Step 15 uses the blue-green chain from b
to g; it separates y2 from r, so swapping yellow and red in the
yellow-red chain through y2 turns y2 red without touching r.

But both chains were found in the ORIGINAL coloring.  The two chains
share the color green, so they can cross each other at green vertices,
and the blue-green chain can run into the region on y1's side of the
red-green chain.  The swap of step 14 then may recolor some of its blue
vertices yellow, and after that the blue-green chain from b to g no
longer exists.  With it goes the barrier that step 15 relied on: in the
new coloring the yellow-red chain through y2 can reach r, and swapping
it turns y2 red but also turns r yellow, so v still has a yellow
neighbor.  (Doing the swaps in the other order fails in the same way.)
Step 16 just assumes that the second swap is still safe after the
first.

That this really happens was shown by Heawood, who gave a map in which
Kempe's double swap fails; smaller examples were found later (one is
the 17-vertex Errera graph).  Heawood's repair of the argument, using
the same chains with five colors, proves the five color theorem, which
is all this method gives.  The four color theorem itself was proved by
K. Appel and W. Haken (1976, published 1977) with a computer check of
an unavoidable set of reducible configurations, and the proof was
simplified by N. Robertson, D. Sanders, P. Seymour and R. Thomas
(1997).
-- Claude (rec.puzzles Oracle, 2026-11-02)