Introduction to the four color theorem:

There are many introduction useful to understand this problem, some of them more formal then others, but all can contribute to give an idea about the problem of coloring maps. I’ve chosen the following introduction, but there are others that can be found here: Links.

From the book “What Is Mathematics”:

”In coloring geographical maps it is customary to give different colors to any two countries that have a portion of their boundary in common. It has been found empirically that any map, no matter how many countries it contains nor how they are situated, can be so colored by using only four different colors. … The fact that no map has yet been found whose coloring requires more than four colors suggests the following mathematical theorem: For any subdivision of the plane into non-overlapping regions, it is always possible to mark the regions with one of the numbers 1, 2, 3, 4 (note: or with four arbitrary colors as red, green, blue, white) in such a way that no two adjacent (whole segment of boundary in common) regions receive the same number (note: or color). … In the four color problem the maps may be drawn either in the plane or on the surface of a sphere. The two cases are equivalent: any map on the sphere may be represented on the plane by boring a small hole trough the interior of one of the regions (named Region-A) and deforming the resulting surface (imagined made of thin rubber) until it stretches out flat on the plan. The resulting map in the plane will be that of an island consisting of the remaining regions, surrounded by a sea consisting of the region Region-A. Conversely, by a reversal of this process …”

Natural language considerations:

Theoretically, any proof may be entirely written in formal mathematical language: stating axioms, logical steps and very few other things. Since it is easier to use a ”natural language” (such as English or Italian) to explain ideas and logical passages, this attempt to prove the theorem will use it whenever the validity of the proof itself won’t be diminished.

Here are some basic vocabulary and examples of their use throughout this notes:

• F = Face; State; Region; Country; The states of a map; The regions of a map
• E = Edge, Boundary of a face; Border of a region
• V = Vertex; Meeting point of the edges of different regions

Examples:

• A map is made of regions or states
• In the process of transforming a map on the sphere into a map on the plane, the face represented by the ocean can be holed and the sphere, imagined to be made of thin rubber, deformed to appear flat
• In a map there are states that have direct access to the ocean (facing the ocean) and states that don’t, as for example Egypt and Chad in Africa

Notes about “Regular maps”, “planar graphs without loops” and formal proof

Real maps can be really strange objects to deal with. They can have holes, enclaves and exclaves, such as Angola in Africa (https://en.wikipedia.org/wiki/Enclave_and_exclave). Luckily, for the scope of the four color problem, many of these situations can be converted into simpler forms or not considered at all. We can also suppose that exactly three edges meet at each vertex, since maps that have vertexes with more than three edges can be easily simplified without affecting the search of the proof. Even if it is not proved here, it is not difficult to show that we can consider as a general case any separation of a plane into contiguous regions (see the book “What Is Mathematics” for details). Such maps are called ”regular maps”.