Định lý năm màu

Định lý năm màu (còn gọi là "định lý bản đồ năm màu"): Mọi đồ thị phẳng (G) đều có số màu formula_1. Là một kết quả từ Lý thuyết đồ thị, cụ thể là mọi bản đồ đều có thể tô bằng năm màu sao cho hai nước nằm kề nhau phải được tô bằng hai màu khác nhau.
Mặc dù đây là định lý yếu hơn định lý bốn màu, nhưng cách chứng minh này cũng đóng vai trò quan trọng bởi vì đây là cơ sở bước đầu để thiết lập cách chứng minh trọn vẹn cho định lý bốn màu mà phải kiểm tra bằng chương trình máy tính.
Dây chuyền luân phiên màu.
Giả sử đồ thị phẳng G đã được tô màu các "đỉnh". Một "dây chuyền luân phiền màu" trong G là một dây chuyền sơ cấp mà các "đỉnh" của chúng được tô bằng 2 màu (trong cách tô màu đang áp dụng cho G).
Giả sử dây chuyền x0 x1 x2... xk là "dây chuyền luân phiên màu" được tô bởi 2 màu W (White) và B (Black) trong cách tô đang dùng cho G. Nếu x0 được tô bởi W thì x1 được tô bở B, x2 được tô bởi W, x3 được tô bởi B... Sở dĩ như vậy vì các "đỉnh kề" nhau phải sử dụng màu khác nhau, mà các "đỉnh" trên dây chuyền này chỉ được tô bởi W và B.
Tính chất của các dây chuyền luân phiên màu.
Vì đang xét "biểu diễn phẳng" (tức là vẽ trên mặt phẳng sao cho không có bất kỳ 2 cạnh nào cắt nhau) của đồ thị nên nếu có hai dây chuyền bất kỳ nào đó cắt nhau thì chúng phải có chung "đỉnh", tức là cắt nhau tại đỉnh chung chứ không thể có hai "cạnh" cắt nhau (do cách vẽ "biểu diễn phẳng" không có bất kỳ hai cạnh nào cắt nhau).
Kết hợp điều này với định nghĩa của "dây chuyền luân phiên màu" ta suy ra tính chất hiển nhiên nhưng quan trọng sau đây:
Hai dây chuyền luân phiên màu" không dùng chung màu thì không thể cắt nhau (vì nếu cắt nhau thì phải có chung "đỉnh", mà "đỉnh" chung đó lại tô một màu nào đó nên hai dây chuyền phải có dùng chung màu)."
Sau đây là một mệnh đề quan trọng liên quan đến "đồ thị phẳng", được sử dụng để chứng minh định lý 5 màu.
Mệnh đề 1.
Giả sử formula_2 là đồ thị đơn, phẳng, liên thông. Khi đó G phải có chứa ít nhất một "đỉnh" có "bậc" nhỏ hơn hay bằng 5.
Tức là: formula_3.
Chứng minh
Giả sử ngược lại: formula_4
Giả sử đồ thị gồm n "đỉnh" và e "cạnh". Nếu số cạnh formula_5 thì điều phải chứng minh là hiển nhiên, ta chỉ xét formula_6.
Áp dụng công thức bậc đỉnh số cạnh và formula_7:
formula_8
Theo hệ quả của công thức Euler: formula_9
Từ đó suy ra: formula_10
Như vậy ta có điều mâu thuẫn, tức là giả sử formula_11 bị sai.
Nhận xét
Mặc dù mệnh đề trên giả sử G là đồ thị đơn, phẳng, liên thông, nhưng nếu G (là đồ thị đơn và phẳng) không liên thông thì mỗi thành phần liên thông của G là đồ thị đơn, phẳng, liên thông: áp dụng mệnh đề trên thì tồn tại "đỉnh" trong thành phần liên thông (cũng là đỉnh của G) có bậc không quá 5.
Như vậy, chúng ta có mệnh đề sau đây.
Mệnh đề 2.
Giả sử formula_2 là đồ thị đơn, phẳng. Khi đó G phải có chứa ít nhất một "đỉnh" có "bậc" nhỏ hơn hay bằng 5.
Tức là: formula_3
Chứng minh định lý 5 màu.
Ta chứng minh quy nạp theo số đỉnh n của đồ thị.
Với n = 1, 2, 3, 4, 5 thì hiển nhiên có thể dùng không quá 5 màu để tô màu các đỉnh theo phép tô màu.
Giả sử rằng mọi đồ thị phẳng có số đỉnh formula_14 đều có thể tô màu "đỉnh" bằng cách dùng không quá 5 màu.
Theo mệnh đề trên G phải chứa một đỉnh x0 mà formula_15
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.
Lúc này ta xét sự tồn tại "dây chuyền luân phiên" màu Blue – Yellow từ y5 đến y3: nếu dây chuyền như vậy tồn tại thì theo tính chất liên tục (xem hình) dây chuyền này phải cắt "dây chuyền luân phiên" màu Green – White: mâu thuẫn với tính chất của "dây chuyền luân phiên màu" bởi vì 2 dây chuyền này không có chung màu. Như vậy:
Không tồn tại dây chuyền luân phiên màu Blue – Yellow từ đỉnh y5 đến đỉnh y3.
Bằng cách lý luận hoàn toàn tương tự như dạng 1, ta có thể thực hiện "phép thay thế màu" sao cho y5 chuyển thành Yellow còn y3 thì vẫn giữ nguyên màu cũ là Yellow. Lúc đó có thể tô x0 bằng màu Blue, nên đồ thị (G) có thể tô bằng 5 màu.
Xem thêm.
Đồ thị
Định lý bốn màu
Tô màu đồ thị