1761561
Định lý năm màu
https://vi.wikipedia.org/wiki?curid=1761561
Title: Định lý năm màu
Gọi G1 là đồ thị có được từ G bằng cách xóa đi đỉnh x0. G1 là đồ thị phẳng có n-1 đỉnh theo giả thiết quy nạp có thể tô G1 bằng cách dùng không quá 5 màu, giả sử formula_16 và xét một cách tô màu G1 sử dụng s màu. Ta xét các trường hợp sau đây:
Trường hợp 1.
Nếu formula_17: chỉ cần lấy cách đang tô cho G1, sau đó tô x0 bằng một màu khác với các màu đã tô cho G1, khi đó ta có cách tô màu G sử dụng formula_18 màu và suy ra: formula_19
Trường hợp 2.
Nếu formula_20 và formula_21: x0 kề với không quá 4 "đỉnh", các "đỉnh kề" với x0 sử dụng chưa hết 5 màu, ta lấy cách đang tô cho G1 và tô x0 bằng màu khác với các đỉnh xung quanh x0 (nhưng vẫn nằm trong số 5 màu đang dùng cho G1). Suy ra: formula_22
Trường hợp 3.
Nếu formula_23 và formula_24. Xét một phép tô màu G1 dùng 5 màu, giả sử ta dùng các màu R (red), W (white), G (green), B (blue), Y (yellow).
Dạng 1.
Không tồn tại dây chuyền luân phiên màu Green – White từ đỉnh y1 đến đỉnh y4.
Ta đặt tập:
"T(y1) = {đỉnh z / có dây chuyền luân phiên Green – White từ y1 đến Z}"
với quy ước T(y1) gồm cả y1 thì tập này có các tính chất:
Từ đó có thể suy ra có thể thực hiện phép thay đổi màu: các "đỉnh" màu Green trong T(y1) tô lại bằng màu White và ngược lại. Phép đổi màu này chỉ làm ảnh hưởng trong nội bộ của T(y1) và không vi phạm nguyên tắc tô màu bởi vì (do các tính chất nói trên của T(y1)):
Sau phép thay đổi màu này thì y1 được tô bằng màu White còn y4 lại vẫn giữ nguyên màu White (do tính chất formula_25): "nhờ vậy ta có thể tô x0 bằng màu Green, nên đồ thị (G) có thể tô màu bằng 5 màu".
Dạng 2.
Tồn tại dây chuyền luân phiên màu Green – White từ đỉnh y1 đến đỉnh y4.