Tô màu đồ thị, định lý bốn màu

Đây là bước khởi động dễ hơn nhiều trước định lý bốn màu: nó chỉ dùng phép quy nạp sơ cấp và một mẹo hoán đổi cục bộ khéo léo (chuỗi Kempe), không cần máy tính hỗ trợ, nên người đọc có thể tự tay kiểm tra từng bước.

Cơ sở quy nạp. Nếu $G$ có nhiều nhất 5 đỉnh, tô mỗi đỉnh một màu riêng; như vậy dùng nhiều nhất 5 màu, khẳng định đúng.

Bước quy nạp, thiết lập. Giả sử mọi đồ thị phẳng có ít hơn $n$ đỉnh đều tô được bằng 5 màu, và cho $G$ là đồ thị phẳng có $n$ đỉnh. Mọi đồ thị phẳng đơn thỏa $E \le 3V - 6$ (chặn cạnh chứng minh nhờ công thức Euler), nên tổng bậc các đỉnh nhiều nhất $2(3n-6) = 6n-12$, nhỏ hơn $6n$. Do đó bậc trung bình nhỏ hơn 6, nên tồn tại một đỉnh $v$ có bậc nhiều nhất 5.

Bỏ $v$ ta được đồ thị phẳng nhỏ hơn với $n-1$ đỉnh; theo giả thiết quy nạp nó có một cách tô hợp lệ bằng 5 màu. Nếu $v$ có nhiều nhất 4 đỉnh kề, các đỉnh kề đó dùng nhiều nhất 4 màu, còn lại một màu tự do cho $v$, xong.

Trường hợp còn lại là deg$(v) = 5$ và cả 5 màu đều xuất hiện, mỗi màu đúng một lần, trong 5 đỉnh kề của $v$. Liệt kê các đỉnh kề theo thứ tự vòng quanh $v$ trong hình vẽ phẳng là thứ nhất, thứ hai, thứ ba, thứ tư, thứ năm, được tô lần lượt màu 1, 2, 3, 4, 5. Xét đồ thị con $H_{1,3}$ gồm mọi đỉnh tô màu 1 hoặc 3. Nếu đỉnh thứ nhất và đỉnh thứ ba nằm ở hai thành phần liên thông khác nhau của $H_{1,3}$, hoán đổi màu 1 và 3 trên toàn bộ thành phần chứa đỉnh thứ nhất; đây vẫn là tô màu hợp lệ (chỉ đụng tới các đỉnh màu 1 hoặc 3), và giờ đỉnh thứ nhất mang màu 3, nên màu 1 tự do cho $v$.

Ngược lại đỉnh thứ nhất và đỉnh thứ ba nằm cùng một thành phần của $H_{1,3}$, nối nhau bằng một đường xen kẽ màu 1 và 3. Cùng với $v$ và hai cạnh tới đỉnh thứ nhất, thứ ba, đường này khép thành một chu trình trong mặt phẳng tách đỉnh thứ hai khỏi đỉnh thứ tư (theo định lý đường cong Jordan, vì thứ tự vòng quanh $v$ là thứ nhất, thứ hai, thứ ba, thứ tư, thứ năm). Do đó không có đường xen kẽ màu 2 và 4 nào nối được đỉnh thứ hai với đỉnh thứ tư, vì đường đó sẽ phải cắt chu trình 1-3. Vậy ta hoán đổi màu 2 và 4 trên toàn bộ thành phần của $H_{2,4}$ chứa đỉnh thứ hai; điều này giải phóng màu 2 cho $v$.

Trong mọi trường hợp $v$ nhận một trong 5 màu mà không xung đột với đỉnh kề nào, mở rộng cách tô của $G$-v ra toàn bộ $G$. Theo quy nạp, $\chi(G) \le 5$ với mọi đồ thị phẳng.

Đây là câu trả lời cho câu hỏi tô màu bản đồ nguyên gốc mà Francis Guthrie đặt ra năm 1852: bốn màu luôn đủ cho mọi bản đồ phẳng, và chặn này chặt, vì một số đồ thị phẳng (chẳng hạn bản đồ có bốn vùng đôi một tiếp giáp nhau) thực sự cần đủ cả bốn màu.

Quy về phản ví dụ nhỏ nhất. Nếu định lý sai, lấy một đồ thị phẳng cần từ 5 màu trở lên với số đỉnh ít nhất có thể. Thêm cạnh vào một đồ thị phẳng mà vẫn giữ tính phẳng chỉ có thể làm tăng số màu cần dùng, nên phản ví dụ nhỏ nhất này có thể coi là một đồ thị phẳng cực đại (một phép tam giác hóa), trong đó mọi miền, kể cả miền ngoài, đều được giới hạn bởi đúng 3 cạnh.

Thiết lập phương pháp xả điện tích. Gán cho mỗi đỉnh $v$ một điện tích ban đầu $6 - \deg(v)$. Dùng $V - E + F = 2$ cùng với $2E = \sum_v \deg(v)$ và $3F \le 2E$ (mỗi miền có ít nhất 3 cạnh), tổng điện tích trên mọi đỉnh tính ra đúng bằng $12$, do đó dương ngặt. Phương pháp xả điện tích sau đó chuyển điện tích cục bộ giữa các đỉnh lân cận theo một tập quy tắc cố định, không làm thay đổi tổng này; phân tích xem điện tích dương còn sót ở đâu sau khi xả cho thấy phải tồn tại một đỉnh bậc thấp cùng một kiểu lân cận cụ thể nào đó xuất hiện đâu đó trong đồ thị. Hữu hạn các kiểu này gọi là các cấu hình không thể tránh, vì ít nhất một trong chúng luôn có mặt trong mọi phép tam giác hóa phẳng.

Tính khử được. Một cấu hình được gọi là khử được nếu, mỗi khi nó xuất hiện trong một phản ví dụ nhỏ nhất giả định, mọi cách tô 4 màu của đồ thị nhỏ hơn thu được bằng cách bỏ hoặc co cấu hình đó luôn có thể mở rộng lại thành một cách tô 4 màu của toàn đồ thị, mâu thuẫn với tính nhỏ nhất. Appel và Haken (1976) đã kiểm tra bằng máy tính rằng mọi cấu hình trong danh sách 1.936 cấu hình không thể tránh của họ (sau này được rút gọn còn 633 bởi Robertson, Sanders, Seymour và Thomas năm 1997) đều khử được, dùng hơn một nghìn giờ máy tính. Điều này khiến định lý bốn màu trở thành định lý lớn đầu tiên có chứng minh dựa cốt yếu vào tính toán máy móc, sau đó được kiểm chứng lại độc lập và, năm 2005, được kiểm tra hình thức từng dòng trong trợ lý chứng minh Coq bởi Gonthier.

Kết luận. Vì mọi cấu hình không thể tránh đều khử được, không thể tồn tại phản ví dụ nhỏ nhất: không đồ thị phẳng nào cần từ 5 màu trở lên, nên $\chi(G) \le 4$ với mọi đồ thị phẳng $G$.