The four-color problem

2.2 Proof of the 4-color theorem
When coloring a map of Kamchatka consisting of 9 regions, in
in any form, without any system, each time there was a failure.
15
Document shared on www.docsity.com
Downloaded by: lochinbek-pardaev ([e-mail])
Then it was decided to start with any area and around it by
clockwise to color adjacent adjacent areas (areas with a common border).
border), so each time expanding the circle to new areas. Then
you were able to colorize the map (see Appendix 1).
But this is not enough for such a statement. Now you need to
consider other map options as well.
You need to solve the following problem: How many countries can
touch each other directly so that all countries have a common border
borders? And, how many colors will it take to color them? "Form" of countries
it may differ from the examples given. The countries are contiguous.
Option 1: two countries can touch each other directly.
Obviously, you need 2 colors (fig. 4).
There are exactly 2 possibilities when 1 or 2 countries are located on
external border.
Figure 3-Two adjacent countries
Option 2: 3 countries can touch directly and converge in one
point.
Since all countries have 2 neighboring countries, 3 colors are needed
(Figure 5).
Figure 4-Three adjacent countries
16
Document shared on www.docsity.com
Downloaded by: lochinbek-pardaev ([e-mail])
There are 3 different options for where on the outer border
there are 1, 2, or 3 countries located.

---

Option 3: It is also possible that 4 countries converge at the same point: in
in this case, you will need 2 colors, but there are only 2 options left. Because
each country has 3 neighboring countries, we need 4 colors.
Figure 5-4 related countries
Answering the question: how many countries are directly adjacent to each other
(i.e., each country shares a common border with the others), one can answer that
the maximum number of such countries is 4.
Then, for paints, the following pattern follows: (Fig. 7a) for n even colors,
3 colors are enough for splits (this is for maps formed by two colors).
concentric circles). And for maps with an odd number of countries
converging at a single point, for n odd partitions (Fig. 7b) - 4 colors
(for maps formed by two concentric circles). Here
note that for maps with an even number of countries (converging in
one point) 4 or more always need 2 colors.
Figure 6-Pattern of paint distribution
17
Document shared on www.docsity.com
Downloaded by: lochinbek-pardaev ([e-mail])
Thus, we can draw the following conclusion: By coloring the maps
with a different number of adjacent countries, will meet mainly 2-
x, 3-color options. Sometimes you will need the 4th color. And the fifth - never. The 
theorem
proven.
18
Document shared on www.docsity.com
Downloaded by: lochinbek-pardaev ([e-mail])