"Proof" of the 4-Color Map Theorem

Proof by Contradiction:

1) We assume that the 4-color theorem is false (i.e., that there exist finite maps 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 finite planar map.

2) There then must exist a counterexample of smallest possible size (i.e. a map with the smallest number of regions that require 5 colors).  Let M be such a "smallest" counterexample.

3) Removing any region from M therefore results in a 4-colorable map.

4) Every region must therefore have valence >= 4 (ie, have 4 or more neighbors) because if such a region existed with a valence less than 4, you could:

a: remove that region from M,

b: 4-color the resulting map (via step 3), and

c: add the region back in, coloring it differently from its <=3 neighbors giving a 4-coloring of M.

5) Every finite planar map contains at least one region of valence <=5. (A proof of this using Euler's formula is straightforward.).  This fact together with step 4 determine that M must contain at least one region of valence 4 or 5.

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

Figure 1: region v has valence = 4

6) Fix a 4-coloring of the map M-v (read "M minus v", the submap of M with v removed).  This must be possible because of the definition of M.  The neighbors of v in M 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 M).

7) Consider the largest connected submap of M that contains region r and only red and green regions.  See figure 1.

8) If that submap does not contain g, then, within that submap, recolor all red regions green and all green regions red.  We now have a 4-coloring of M-v in which no neighbor of v is red.  Therefore coloring v red results in a 4-coloring of M.  Contradiction.

9) The contradiction in step 8 shows that the submap in step 7 must contain g.  Therefore there exists an alternating path of red and green regions that divides M-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 regions blue and all blue regions yellow.  We now have a new 4-coloring of M-v in which no neighbor of v is yellow.  Therefore coloring v yellow results in a 4-coloring of M.  Also a contradiction.  CASE 1 leads to a contradiction either way, so it must be false.

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

11) As in step 6, fix a 4-coloring of the map M-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.
 

Figure 2a: region v has valence = 5 and is surrounded by ryygb

13) The final possibility to examine is where the neighbors of v are colored rygyb.

Figure 2b: region v has valence = 5 and is surrounded by rygyb

14) The alternating red-green path between r and g which isolates the first y region from b must exist by the same reasoning as for CASE 1. This means that the yellow and blue regions in the area containing the first y region can swap colors, turning that yellow region blue.

15) Likewise, the same argument can be used to show that there must exist a path of alternating blue-green regions from b to g which isolate the second y region from r. This means that the yellow and red regions in that region can swap colors, turning that y region red.

16) Because steps 14 and 15 allow us to recolor both y regions to other colors, we can arrive at a 4-coloring of M-v in which no neighbor of v is yellow. Therefore coloring v = yellow results in a 4-coloring of M. This proves that CASE 2 must also be false.  Since both cases are false, M (which was any smallest counter-example) cannot exist proving that there can be no counter-examples, and that all finite planar maps must be 4-colorable.