Given a geographic map, a k-coloring assigns one of k colors to each region, so that adjacent regions have different colors. Adjacent regions must share a border, not just a point. The problem is to find the minimum k that will color the map.
Turn the map into a graph, so that regions become points and borders become connecting edges. If the graph is not connected, as though the oceans between continents didn't matter, color each component separately. Thus we will deal with connected graphs only.
Trim off dangling trees. Once the remaining graph has been colored, the adjoined trees can be colored using only two colors. Since there are no cycles, there are no conflicts.
Every planar graph can be colored using 5 colors.
First review Euler's formula, which proves there must be some vertex somewhere with degree < 6. Let x have degree 5 or less. If x has degree 4 or less, color the rest of the graph and assign x the fifth color. (We can do this by induction; graphs with fewer vertices can be colored.) The only difficult case is when x has degree five.
Ignore x and color the rest of the graph with 5 colors. If 4 or fewer colors are connected to x, give x the fifth color. Otherwise let the colors run red orange yellow green blue clockwise around x. Boldly switch red to yellow, adjacent yellows to red, adjacent reds to yellow, etc. This allows us to color x red, unless there is a path from red to yellow containing red and yellow vertices. If the chain exists then change orange to green, adjacent greens to orange, etc. This orange green subgraph will never reach the green adjacent to x, for the red-yellow chain separates the orange and green vertices. Color x orange and we are done.
Note, if the graph is not planar, coloring the graph, even with three colors, is np complete.
In fact, 4 colors are sufficient. The above can be extended into a 4 color proof, which is compelling, but not quite right. See if you can spot the error.
If a vertex has degree 4, with red yellow blue green around, change red to blue, and if this chains around and turns blue to red, change yellow to green and make x yellow.
The only tricky part is when x has degree 5, and 4 colors are involved. Place blue at the top, reds on either side, and yellow and green at the bottom, like a colorful starfish. Change blue to yellow. This solves the problem, unless there is a blue-yellow chain around. Change blue to green, and again suppose there is a troublesome blue-green chain. Change the left red to green. This is trapped by the blue-yellow chain, and cannot snake around to the red / green arms on the other side. Then change the right red to yellow. This is trapped by the blue-green chain, and cannot bother the yellow on the left. Finally paint x red, and we're done.
Do you see the problem? The blue-yellow and blue-green chains can intersect, and cross each other several times. When you change the left red to green, this can break the blue-green chain by chainging one of the greens to red; and this happens before you run into the blue-yellow chain. Then when you change the right red to yellow, there is no blue-green chain to contain it. It can snake around and change the yellow arm to red.
The four color theorem is true, but the proof involves many subgraphs that can only be analyzed by a computer. We'll look at some of these in a minute, but first let's rule out some bands.
Suppose one country runs around the equator, between 10 degrees north and 10 degrees south. Throw away all the countries in the southern hemisphere and spread this band over half the Earth. This is a smaller graph, fewer countries, and four colors will do. Make the equatorial country red. Then throw away the northern countries and do the same thing. You have colored each half of the planet separately, and the common country, at the equator, is red. Put this all together and you have colored the map.
Let two regions wrap around the Earth to form an equatorial band. Throw away the countries below, color the northern graph, and paint the regions red and blue. Do the same for the southern graph and put everything together.
A band of three countries is colored red blue green from the north and the south, and is thus ruled out. This assumes there are countries above and below, so that each subgraph is actually smaller, and can be colored. You can't just walk around a triangle and call it a band.
Suppose four countries form a band around the Earth. Throw away the southern countries and connect the two regions on the left and the right across the south pole. Color the map and paint these regions red and blue. I will call this a "northern" coloring, since I have retained the northern hemisphere and simplified the southern in some way. Now the equatorial regions in front and back have to be green or yellow. If both colorings, from the south and from the north, allow these regions to agree, or disagree, we're ok. So let the northern coloring c1 force the regions to be yellow, thanks to a yellow green chain across the north pole, and let the southern coloring c2 force the regions to be yellow and green, thanks to a yellow green chain across the south pole. Recolor the north c3 with the front and back regions connected across the south pole. Now they are yellow and green, just like the southern coloring c2. Combine c3 with c2. If the left and right regions in c3 are red and blue respectively, we're all set. Otherwise change the left and right regions in c2 to match the colors in c3. We can do this because of the yellow green chain that runs across the south pole.
This rules out graphs with connectivity ≤ 4. We will now extend this to 5, provided neither of the separated components is a single point.
Suppose there is a band of 5 countries around the equator. Further suppose there is more than one country above and below. The band does not simply surround a single country.
Replace the southern hemisphere with one country, which will be green, and color the simplified map c1, whence the equator runs red blue yellow blue yellow around. The only parameter here is where the odd color, in this example red, is located. There are 5 choices. If we similarly color the southern hemisphere c2 and red winds up in the same position then we're done.
Odds are, the reds will be out of position. Start with the southern coloring c2 and try to migrate red clockwise (as viewed from above). Basically we are switching red with the adjacent blue, and leaving yellow blue yellow alone. Then switch red with yellow, etc. Keep doing this until the odd color lines up with its counterpart from c1. Perhaps we have already done this k times, still not matching c1, (whence k < 4), but now we are blocked by a red blue chain running around the south pole to the blue across the way. In that case we have the option of turning the yellow (between the blues) to green, thus creating a 4 color pattern. Try to match this pattern upstairs.
Remove the southern countries and sew the two blue points together. (They are not connected by an arc; they are actually the same point.) Color the northern half of the sphere c3 and of course these points will have the same color; call it blue. Let the other two points in the triangle be yellow and red, just like they are downstairs. That leaves the tail of the triangle. If it is yellow we match the 3 color pattern from the south, and if it is green we match the derived 4 color pattern from the south. Put those together and we're done. If it is red then the odd color, in this case yellow, is nextdoor to red downstairs. If k > 0, if we were able to migrate clockwise at all, then this matches where we just came from. c3 agrees with c2 one tick in the past. Put those together and we're done.
Suppose we couldn't even get started. Perhaps k = 0; perhaps our first step clockwise didn't work. We were blocked by a red blue chain across the south pole. Try to migrate red counterclockwise instead. The same logic applies. You will either move around to match c1, or be blocked, and then the new pattern c3 will match what you have, or where you just came from. Thus red is locked in, that is, it can't migrate left or right.
Suppose this is the case from the north and from the south. Red from c2 can't move clockwise, and c3 didn't help us, which means it presents red blue red blue yellow. This might not be c1, but it's there, so let's use it. Relable it to be yellow blue yellow blue red, so red is again the odd color. Red must be locked in, as described above. Red can't move counterclockwise in c3, just as red can't move clockwise in c2. A red blue chain runs across the south pole, preventing that migration, and a red blue chain runs across the north pole, preventing that migration. Change the yellow, between the blues, to green, in both c2 and c3. Interchange red and yellow in c2 so they agree with c3. Put these together and we're done. There is no band of 5 unless it surrounds a single country.
Start at a point in an uncolorable graph G, and wander around locally, building a subgraph H. Let the diameter of H be 4 or less. There can be no connection from any point of H, around the back of the sphere, and back to H, as that would create a band of length 5 or less. Thus H has a well defined border that is not part of H.
If G is the smallest uncolorable graph, then remove H and color what remains; then try to color H in a compatible manner. Since the border of H is distinct from H, these operations are well defined.
Granted, two border points, say u and v, could connect from behind, giving a band of length 7. In that case u and v would have to obtain different colors. But if we consider all color patterns for the border, then we have certainly considered those patterns wherein u and v disagree.
If u and v coincide, we have a band of length 6. Again, we are considering all color patterns, including those wherein u and v agree.
It is possible to replace H with some connectin lines among the border points, i.e. triangulation, or even any subgraph with fewer points than H. You could for instance replace H with a single point that is connected to all the border points. Color G, and you only need consider the 3 color patterns around the border. For each of these, try to color H in a compatible manner.
Assign colors to the ring around H, and if H cannot be colored directly, try changing some of the colors, as we did when proving the 5 color theorem. Watch out for chains, which can obviate your change.
Assume it would be helpful to change a certain point from red to blue. This may cause other reds or blues to switch, while yellows and greens are unaffected. An arc is a continuous sequence of red or blue points, or yellow or green points, around H. If the ring consists of one arc, then making the change is no change at all. We have merely relabled red as blue and blue as red. Thus we will assume the ring has at least 2 arcs. Notice that the number of arcs is now even.
If there are 2 arcs, then changing red and blue is again a relabeling that makes no difference.
Assume there are 4 arcs. Switching one of the red blue arcs might allow H to be colored, but what if this forces, via a connecting chain, the other red blue arc to switch? That is merely a relabeling. The yellow green arcs are now separated by a red blue chain, and are independent. Change either of the yellow green arcs and see if that allows H to be colored. It doesn't matter which one we change. Therefore this pattern, which at first does not seem to facilitate H, in fact leads to a coloring of H, if one of the red blue arcs (when changed) leads to success, and if one of the yellow green arcs (when changed) also leads to success.
Hereafter I will call them red arcs (for red blue) and yellow arcs (for yellow green).
Assume there are still 4 arcs: red yellow red yellow, and perhaps changing a red arc and yellow arc simultaneously does the trick. This is thwarted only if a chain snakes around from one arc to the other side, and if that happens we could change the red arc, or yellow arc, independently. Hopefully that will turn the trick. So we have the same formula for success: 2 adjacent arcs that when flipped individually and independently, yield success. In other words, 2 in a row.
Changing a red arc has the same effect as changing the opposite arc, so 2 in a row implies all 4, hence you can test for any 2 adjacent arcs.
Assume there are 6 arcs. Remember that changing one red arc is the same as changing the other two. So assume switching the first red arc does the trick. That's fine unless there is a chain around to the second or the third. In that event we can switch the yellow arc on either side of the red arc. If those two lead to success then we have three arcs in a row, and that does the trick.
Suppose two adjacent arcs flip and that is success. Chains might force either of the other red arcs to flip, or either of the other yellow arcs to flip. We don't know the chains in advance, so we might be flipping any of 4 arcs to save the day. 4 arcs in a row is a stronger condition than 3 in a row, so just go back to 3 in a row.
Finally assume changing a red arc and the ywllo arc opposite does the trick. Chains could snake around from either of these arcs, so we might have to flip any of the other 4 independently. Well that's not 3 in a row, so this is a new condition: opposite arcs together, or the other 4 independently.
If flipping a red arc works, that doesn't mean flipping another red arc would work. You would have to flip the other two red arcs. Thus you can't just test for any 3 in a row, you have to test all 6 and look for 3 in a row.
Suppose four points of degree 5 are arranged in a diamond. This looks like two triangles sharing a common side, one pointing left and one pointing right. Label the left vertex A and the right vertex D. The top vertex is B, and the bottom is C. Thus BCA and BCD are the two triangles. This is our subgraph H.
Place a ring of 6 points around H, with three points connected to A and three points connected to D. The top two points are connected to B, and the bottom two points are connected to C. Number the points 0 through 5, clockwise, starting at the upper right. Thus 0 through 2 connect to D, and 3 through 5 connect to A.
Adjusting for reflections and rotations, there are 15 distinct color patterns. Let's list them in an order that is convenient for human categorization. (A computer would probably crank them out lexicographically.) Patterns with 3 of a kind - may as well be three reds in positions 1 3 and 5: brbrbr, brbrgr, brgrbr, and brgryr. (I'll try to keep r in position 5 as we go.) Patterns with three pairs: bgrbgr, bgbrgr, and brgbgr. everything hereafter is two pair and two singles. Patterns with red above and below, in positions 5 and 3: bgbryr, bygrbr, and ybgrbr. Patterns with red at the top and at the right: brgbyr, brgybr, and grbybr. Remaining patterns: bgrbyr and gbrybr. Yes, there are 15.
The patterns with 3 of a kind cannot be tackled first, so let's set those aside. Assume A vertex above and below have the same color, such as 3 = 5 = r. If the colors run bgbrgr, set A = b, D = r, B = g, and C = y. Similarly for bybrgr, bygrgr, and ygbrgr. These are all directly colorable.
Three other patterns that are directly colorable are: yrbrbr, brgbgr, and brgygr. The first of these has three reds. Another three reds is brbrgr. Change the rightmost r to y, and if that chains around to the red above or the red below or both, change one b to g. The implied patterns are colorable, hence brbrgr is also colorable. This is the first indirectly colorable pattern.
The next 3 red pattern is brgryr. Change the rightmost r to y, and if this fails, change b to g or g to b, giving the previous pattern.
The last 3 red pattern is brbrbr. Change b to y, leaving 3 reds. If this fails, change a neighboring r to g, leaving three blues. That finishes the 3 of a kind patterns.
Let a pair have the same color from a top vertex to the far side. thus 5 = 1 = r. Some of these patterns have been covered; let's see what's left. We've already ruled out equal colors above and below, so 0 and 2 are different. Let 0 and 3 be the same, hence brgbyr. Change b to r on the bottom, giving three reds, and if this fails change y to g. Then let 0 and 4 be the same, hence brgybr. Swap g and r to get the previous pattern, or swap b andy, which is also the previous pattern. That takes care of 0 being the same as something else. And this in turn is the last pattern with r in positions 5 and 1.
There are two more ways to have two pairs and two singles, and one pattern remaining with three pairs. Start with byrbgr. Swap b and y, or change r to g.
consider the 3 pair pattern bgrbgr. Swap b and r on the bottom, and if this fails, change g to y.
Finally consider bgrygr. Swap r and b on top, or change g to y.
That is all the patterns, thus the 5 diamond never occurs. The smallest uncolorable graph, i.e. graph requiring 5 colors, cannot contain 4 vertices of degree 5 arranged in a diamond.
If you actually followed all this, then you can appreciate the value of a computer doing all the bookkeeping for you. In the 1970s the four color theorem was proved with the help of a computer. This was somewhat controversial at the time, but like similar proofs, it has since been widely accepted. There is no special reason that a proof should be of a certain length, or fit within the confines of the human mind. In fact it would be surprising if every true statement admitted a concise paper and pencil proof.
Assume there are 8 arcs around. Changing the first one is good, but it could snake around to any or all of the other three. If it chains to the opposite red arc, then we might need to change both yellow arcs on one side, they may be connected, or both yellow arcs on the other side, which is the same thing. So we need yellow red yellow independently, and yellow plus the next yellow over.
Flipping adjacent red and yellow arcs doesn't profit us, just as it didn't before. We must guard against the red chains, so all the prior yellow conditions hold, and we must guard against the yellow chains, which means red might flip on its own, and that reproduces the above paragraph.
Try to flip a red arc and the next red arc over. They might be connected or not; it doesn't matter we are flipping them both. But either red arc could chain to the other one around, or the one across. We must be prepared to flip the yellows outside of the two red arcs independently, plus the two top yellows together, and the two right yellows together.
Flip a red arc and the opposite red arc and call that good. To guard against chains, any of the four yello arcs could flip independently.
The last case I'll consider, and not the last case there is, is changing three in a row, red yellow red. These two reds may be connected or not. But either could chain around to the other reds, so the yellows next to this triple might flip independently, or the top pair of yellows, or the right pair of yellows. If the yellow inside the triple snakes around, we might flip either of the reds independently, or the red and the next red around.
A general algorithm applies for n arcs. I will present an outline of the algorithm here.
Assume arc 0 is connected, by chains, to various other red arcs. If the first of these is 4, then 1 and 3 are yellow arcs, and they must connect to each other, else the red arc at 2 would expand until it touches the chain that joins 0 and 4. So 1 and 3 are connected, and 2 stands alone. If there is another red arc in the first set, say 12, then 5 and 11 are connected, but we have choices for the 2 yellow arcs between 5 and 11. Any of these could be connected to the 5 11 chain. There are 4 possibiliities here. If neither 7 nor 9 is connected, then the next chain inside joins 6 and 10, and perhaps 8. Run through all these possibilities, then go back and pick another red connecting set at the start, then another, then another. Allow for the possibility that no reds are connected, whence all the yellows are connected.
For each configuration, flip the arcs in all possible ways, realizing that connected sets must flip as one. If any of these flips allows H to be colored, then that configuration is good. If all configurations are good then any coloring of G without H extends to H, and G cannot be the smallest uncolorable graph.
Let H be an octagon with 5 5 6 5 5 around. Remove H and color G in all possible ways. We are interested in the 10 point ring that surrounds H. Set aside those patterns that will extend to H, either directly or after the chaining transformations described above. Many uncolorable patterns remain. This looks formidable, but in each case the color of vertex 0 is the same as the color of one of the vertices from 2 to 6. Connect vertex 0 to 2 3 4 5 6, recolor G, and all the uncolorable patterns go away. The remaining patterns extend to H. Therefore the smallest uncolorable graph cannot contain H.
Remember that we can replace H with other graphs, as long as they have fewer points than H.
If the border is a triangle, there is no reason to replace H with anything. The ring is colored red blue green, and if a subgraph would impose any additional restrictions, then that graph, smaller than G, is uncolorable. This may seem silly, because the border of H is not going to be a triangle. We already ruled out a band of length 3. But this does come into play as you build a new graph that replaces H. If x is placed in the center, (replacing H with a single point), and you connect x to everything around, there is no reason to add any more points. Wherever you put y, it will land inside a triangle, and that will not restrict the patterns any further.
Assume we are refining the new graph by adding points to a square. Adding a diagonal makes opposite ends different, and adding x in the center forces 3 colors. The latter will not be necessary, as sewing opposite corners together is a stronger constraint (see below). If there are two points inside, let x connect top left, top right, and lower right, and let y connect bottom left, bottom right, and upper left. This is uncolorable only if upper right equals lower left, and we can rule that out with a diagonal. In general, I'm going to draw a diagonal in the square, or sew.
It is possible to sew nonadjacent vertices of the ring together, and then color the rest of G. For instance, draw adjacent triangles BCA and BCD as we did before, but this time B and C have degree 6, while A and D still have degree 5. Without H, the ring consists of 8 points. Sew the points connected to B (but nonadjacent) together, and sew the points connected to C (but nonadjacent) together. The ring looks like a square with a tail above and below. Draw a vertical line to connect these merged points so they must have different colors. Now color G; each of the patterns extends to H.
If we care to use this trick, the sewn together points can create a vertex with higher degree than any in the original graph. The same holds for drawing internal edges. The smallest uncolorable graph won't have H, but it might have vertices whose degree exceeds those in H.
A vertex of degree n contributes n/2 edges, and n/3 faces. Substitute in euler's formula and get 1 - n/2 + n/3 = 1-n/6 = (6-n)/6. To avoid fractions we'll just say each vertex contributes 6-n, and the total has to equal 12. Each hexagon (degree = 6) contributes nothing. Each pentagon contributes 1, and everybody else is negative. (When I use the word pentagon I'm referring to a country on the original map that borders 5 others; that's easier than saying "a vertex of degree 5".) You need at least 12 pentagons to reach 12. This is the dodecahedron, which is colorable. Each vertex of degree higher than 6 requires more pentagons to compensate. A decagon, for instance, demands four more pentagons somewhere on the map.
What can we put around a pentagon? Not three pentagons in a row, as that would create a diamond (as described above).
Two nonadjacent pentagons must have hexagons in between. This is ruled out by computer (p565 p5665 p56665). One pentagone and four hexagons is also ruled out (p56666), and a ring of five hexagons is also out (p66666).
The smallest uncolorable graph has at least one vertex of degree ≥ 7. In fact each pentagon is adjacent to one of these higher vertices.
Remember, an uncolorable graph could consist entirely of hexagons and pentagons, but it won't be the smallest example.