Định lý năm màu

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.