Korean, Edit

Four Color Theorem

Recommended post: 【Modern Mathematics】 Graph Theory

1. Theorem

2. Proof

1. Theorem

Every planar map can be colored with only four colors so that adjacent regions have different colors

2. Proof

⑴ 1^st. Convert the map into a graph

① Treat each region as a point, and connect them with a line if they share a border

② The given problem is transformed into whether every planar graph is vertex 4-colorable

⑵ 2^nd. Make the given planar graph like a triangulated planar graph

① Example

# Before
A────B
│    │
│    │
D────C

# After
      A
     /|\
    / | \
   B--D--C
    \   /
     \ /
      C and B connect along the outer side

② If every triangulated planar graph is 4-colorable (the harder problem), then every planar graph is also 4-colorable (the easier problem)

⑶ 3^rd. Search for some unavoidable sets sufficient for the proof

① Unavoidable set: A collection of structures such that, no matter what planar graph is given, at least one of them must necessarily be included in that graph

○ In Appel–Haken’s 1976 proof, about 1,834 reducible configurations were checked by computer (ref)

○ Later, through some refinements, this was reduced to 1,482 (ref)

○ Robertson, Sanders, Seymour, and Thomas reduced it to 633 in 1997 (ref) → The following explanation will be standardized as 633

② Example 1. The simplest unavoidable set

○ Sum of the boundary lengths of all faces = 2E ≥ 3F ⇔ F ≤ 2E / 3

○ 2 = V - E + F ≤ V - E + 2E / 3 ⇔ E ≤ 3V - 6

○ If we assume that every vertex has degree at least 6, then the total degree sum = 2E ≥ 6V ≥ 2E + 12 (contradiction)

○ In a planar graph, there must be at least one vertex of degree 5 or less

○ Unavoidable set = {degree 1 vertex, degree 2 vertex, degree 3 vertex, degree 4 vertex, degree 5 vertex}

③ Example 2. Discharging method

○ If charge is defined as 6 - degree, then the total charge sum = ∑(6 - degree) = 6V - 2E = 6V - 2(3V - 6) = 12

○ While maintaining the total charge of 12 derived from Euler’s formula, move the charge according to fixed rules (they may be chosen arbitrarily as long as they are consistent)

○ Corresponding to the fixed rules, 633 local patterns with positive charge remaining were found (using a computer)

○ A graph without the 633 local patterns has all charges less than or equal to 0

○ Since the total charge sum is 12, not all charges can be less than or equal to 0

○ Therefore, one of the 633 structures must necessarily exist

⑷ 4^th. Proof by contradiction: Assume that there is a planar graph that cannot be 4-colored, and among them, take a minimal counterexample with the smallest number of vertices

① In the minimal counterexample, whether one of the 633 structures is removed or not does not change whether the four color theorem holds (reducible)

② Case 1. If something remains after all 633 structures are removed from the minimal counterexample, this violates the preceding discharging method, giving a contradiction

③ Case 2. If nothing remains after all 633 structures are removed from the minimal counterexample, this itself means that the four color theorem holds, contradicting the fact that it is a counterexample

⑸ 5^th. Therefore, no such counterexample exists, and consequently the four color theorem holds

⑹ Summary

Input: 2026.02.07 11:10