"Proof" of the 4Color Map Theorem
3) Removing any region from M therefore results in a 4colorable 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:
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 
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 4coloring of Mv in which no neighbor of v is red. Therefore coloring v red results in a 4coloring 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 Mv 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 4coloring of Mv in which no neighbor of v is yellow. Therefore coloring v yellow results in a 4coloring 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.

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

Figure 2b: region v has valence = 5 and is surrounded by rygyb 
14) The alternating redgreen 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 bluegreen 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 4coloring of Mv in which no neighbor of v is yellow. Therefore coloring v = yellow results in a 4coloring of M. This proves that CASE 2 must also be false. Since both cases are false, M (which was any smallest counterexample) cannot exist proving that there can be no counterexamples, and that all finite planar maps must be 4colorable.