Four color theorem

The four color theorem says that you only need four colors to color any map. This means that no two places that share a border can have the same color. It sounds easy, but it was very hard to prove.

The four color theorem is a harder version of the five color theorem, which is easier to show is true. Many people tried to prove the four color theorem for a long time. In 1976, Kenneth Appel and Wolfgang Haken finally proved it. They used a computer-aided proof, which was new and exciting at the time.

At first, some mathematicians were not sure, but the proof became accepted. In 2005, Georges Gonthier checked the theorem again using special theorem-proving software, making it even more certain.

Formulation

The four color theorem tells us that when coloring a map, we only need four colors so that no two areas sharing a border have the same color. This idea can also be explained using graph theory, where each area on the map is a point, and lines connect points of neighboring areas. The theorem shows that these points can always be colored with just four colors so that no connected points share a color. This was an important discovery because it was the first time a computer helped prove a big mathematical idea.

History

The four color theorem says that any map can be colored with just four colors. No two areas that share a border will have the same color.

This idea was first noticed in 1852 by Francis Guthrie. He saw that a map of the counties of England needed only four colors.

Many people tried to prove this idea was true, but made mistakes. One famous try by Alfred Kempe in 1879 was thought to work, but it was later found to be wrong.

In 1976, Kenneth Appel and Wolfgang Haken finally proved the theorem true. They used a computer to check many cases. This was the first big math problem solved with a computer. It showed that no map needs more than four colors.

Summary of proof ideas

The four color theorem says that you only need four colors to color any map so that no two areas that share a border have the same color. Early tries to prove this, like one by Kempe, had mistakes but helped people learn useful things.

To prove the theorem, mathematicians think of maps as networks of points and lines, called graphs. They show that if a map can be turned into triangles without changing how it is colored, then proving it for these triangle maps proves it for all maps. By using a rule called the "method of discharging," they can find important patterns that must be in any map. Checking these patterns shows they can always be colored with four colors, finishing the proof.

False disproofs

The four color theorem has had many wrong proofs and disproofs over time. Some famous wrong proofs, like Kempe's and Tait's, were looked at by people for more than ten years before it was found that they were incorrect. Many other wrong proofs were never even shared.

A common mistake when trying to disprove the theorem is to make a map where one big area touches all other areas. This might look like it needs more than four colors, but the other areas can always be colored with just three colors. People often miss this because they only look at the big area and don’t rearrange the colors. Another mistake is not knowing that areas only need different colors from the areas they touch directly, not from areas that touch other areas. Some wrong disproofs also break the theorem’s rules, like using areas with more than one part.

Three-coloring

Some maps can be colored using only three colors. But it is hard to know if a map can be colored with just three colors.

For some maps called cubic maps, three colors are enough if each area touches an even number of other areas. For example, the state of Missouri can be colored with three colors because it touches eight other states. But if an area touches an odd number of other areas, like Nevada which touches five states, four colors are needed.

Generalizations

The four color theorem works for flat maps and also for very large maps that can be drawn without lines crossing. This idea can be used for many different kinds of maps.

When thinking about coloring maps on surfaces other than flat paper, like balls or curved shapes, more colors might be needed. For example, coloring a map on a ball is the same as coloring a flat map, but a map on a shape with tunnels might need up to seven colors. Some special shapes, like the Klein bottle, need just six colors even though a quick calculation might suggest they need seven.

Relation to other areas of mathematics

The four color theorem is linked to other parts of mathematics. A mathematician named Dror Bar-Natan showed that a statement about special math structures called Lie algebras and Vassiliev invariants is really the same as the four color theorem. This shows how different areas of math can connect in interesting ways.

Use outside of mathematics

The four color theorem is about coloring maps so that no two neighboring areas share the same color. However, map makers don’t use it much because most real maps need only three colors. Also, this rule only works for areas that touch each other directly. It doesn’t work for maps of the whole world, where far apart parts of a country need to be the same color.

Sometimes, special rules make it harder to color a map with just four colors. For example, if all oceans must be one color, like blue, and countries next to each other need different colors, some maps need more than four colors to follow all the rules.