Đị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 x x x... x 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 x được tô bởi W thì x được tô bở B, x được tô bởi W, x đượ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 x mà formula_15

Gọi G là đồ thị có được từ G bằng cách xóa đi đỉnh x. G là đồ thị phẳng có n-1 đỉnh theo giả thiết quy nạp có thể tô G 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 G 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 G, sau đó tô x bằng một màu khác với các màu đã tô cho G, 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: x kề với không quá 4 "đỉnh", các "đỉnh kề" với x sử dụng chưa hết 5 màu, ta lấy cách đang tô cho G và tô x bằng màu khác với các đỉnh xung quanh x (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 G dùng 5 màu, giả sử ta dùng các màu R (red), W (white), G (green), B (blue), Y (yellow).

- Nếu 5 đỉnh xung quanh x chưa dùng đủ 5 màu này: ta chỉ tô x bằng màu chưa dùng và suy ra có thể tô (G) bằng 5 màu.
- Nếu 5 đỉnh xung quanh x dùng đủ 5 màu này: đây là trường hợp chúng ta sẽ sử dụng "phép thay thế màu" nhờ dựa vào các dây chuyền luân phiên màu. Không mất tổng quát có thể giả sử các màu tô các đỉnh kề với x được bố trí như hình ảnh. Ta xét hai dạng loại trừ nhau như sau:

==== Dạng 1 ====
Không tồn tại dây chuyền luân phiên màu Green – White từ đỉnh y đến đỉnh y.

Ta đặt tập:

"T(y) = {đỉnh z / có dây chuyền luân phiên Green – White từ y đến Z}"

với quy ước T(y) gồm cả y thì tập này có các tính chất:

- T(y) không chứa y: formula_25.
- Các "đỉnh" thuộc T(y) chỉ được tô bằng hai màu Green và White.
- Với mọi đỉnh v kề với một đỉnh nào đó của T(y) nếu v tô bằng màu khác với Green, White thì formula_26, còn nếu v tô bằng một trong hai màu này thì suy ra formula_27.
- Đỉnh y không kề với bất kỳ đỉnh nào của T(y) vì nếu ngược lại thì theo tính chất trên ta suy ra formula_28 mâu thuẫn với tính chất đầu tiên.

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(y) 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(y) 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(y)):

- Các "đỉnh kề" nhau trong T(y) thì đã hoán vị màu
- Các "đỉnh kề" với "đỉnh" của T(y) mà không thuộc về T(y) thì lại có màu khác với Green, White.

Sau phép thay đổi màu này thì y được tô bằng màu White còn y lại vẫn giữ nguyên màu White (do tính chất formula_25): "nhờ vậy ta có thể tô x 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 y đến đỉnh y.

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ừ y đến y: 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 y đến đỉnh y.

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 y chuyển thành Yellow còn y thì vẫn giữ nguyên màu cũ là Yellow. Lúc đó có thể tô x 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ị

== Tham khảo ==
- (= "Indag. Math." 13)