Four color theorem

In mathematics, the four color theorem states that no more than four colors are needed to color any map so that no two neighboring areas share the same color. Two areas are neighbors if they share a border, not just a point where three or more areas meet. This idea might seem simple, but proving it was a big challenge for mathematicians.

The four color theorem is a stronger version of the five color theorem, which is easier to prove. People tried to prove the four color theorem for many years, but it wasn’t until 1976 that Kenneth Appel and Wolfgang Haken finally did it using a computer-aided proof. Their work was special because it was one of the first major theorems proven with the help of a computer.

Even though some mathematicians were unsure at first, the proof has become widely accepted. Later improvements reduced the number of special cases that needed checking. In 2005, the theorem was verified again using special theorem-proving software by Georges Gonthier, making it even more certain.

Formulation

The four color theorem tells us that when coloring a map, we only need four colors to ensure 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 a big discovery because it was the first time a computer helped prove a major mathematical idea.

History

The four color theorem, which says that any map can be colored with just four colors so that no two neighboring areas share the same color, was first noticed in 1852 by Francis Guthrie. He saw that a map of the counties of England needed only four colors. Later, mathematicians tried to prove this idea was true.

Many early attempts to prove the theorem failed. One famous try by Alfred Kempe in 1879 was thought to work until 1890, when another mathematician showed it had a mistake. In 1976, Kenneth Appel and Wolfgang Haken finally proved the theorem true, but they used a computer to check many cases. This was the first major math problem solved with a computer, and it showed that no map needs more than four colors.

Summary of proof ideas

The four color theorem tells us that we only need four colors to color any map so that no two neighboring areas share the same color. Early attempts to prove this, like one by Kempe, had mistakes but gave useful ideas.

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

False disproofs

The four color theorem has often attracted many incorrect proofs and disproofs throughout its history. Some famous alleged proofs, like Kempe's and Tait's, were examined by the public for over ten years before being shown to be wrong. Many other incorrect proofs were never even published.

A common mistake in trying to disprove the theorem is to create a map where one large region touches all other regions. This might seem to require more than four colors, but in reality, the remaining areas can always be colored with just three colors. People often miss this because they focus only on the large region without rearranging the colors. Another mistake is not understanding that regions only need to be different colors from the areas they touch directly, not from areas that touch other areas. Some false disproofs also break the theorem's rules, like using regions with multiple disconnected parts.

Three-coloring

Some maps can be colored using only three colors, but deciding whether any given map can be colored with just three colors is very difficult.

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

Generalizations

The four color theorem works not only for flat maps but also for infinite maps that can be drawn without lines crossing. This idea can be expanded to 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 connects to other parts of mathematics. A mathematician named Dror Bar-Natan showed that a statement about certain mathematical structures called Lie algebras and Vassiliev invariants is actually the same as the four color theorem. This shows how different areas of math can sometimes relate to each other in surprising 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.