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

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". ]