Đị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

\gamma (G)\leq 5\,

. 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[sửa | sửa mã nguồn]

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_k 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[sửa | sửa mã nguồn]

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)^[1] 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[sửa | sửa mã nguồn]

Giả sử $G=(X,E)$ 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à: $\exists x\in X,d_{G}(x)\leq 5$ .

Chứng minh

Giả sử ngược lại: $\forall x\in X,d_{G}(x)\geq 6\ \ \ \ \ \ (\alpha )$

Giả sử đồ thị gồm n đỉnh và e cạnh. Nếu số cạnh $e\leq 2$ thì điều phải chứng minh là hiển nhiên, ta chỉ xét $e>2$ .

Áp dụng công thức bậc đỉnh số cạnh và $d_{G}(x)\geq 6,\forall x\in X$ : $6n=\sum _{x\in X}6\leq \sum _{x\in X}d_{G}(x)=2e$

Theo hệ quả của công thức Euler: $e\geq 3n-6$

Từ đó suy ra: $6n\leq 2e\leq 2(3n-6)\Rightarrow 6n\leq 6n-12\Rightarrow 0\leq -12(!)$

Như vậy ta có điều mâu thuẫn, tức là giả sử $(\alpha )$ 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[sửa | sửa mã nguồn]

Giả sử $G=(X,E)$ 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à: $\exists x\in X,d_{G}(x)\leq 5$

Chứng minh định lý 5 màu[sửa | sửa mã nguồn]

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 $k<n$ đề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à $d_{G}(x_{0})\leq 5.\,$

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ử $s=\gamma (G_{1})\leq 5$ 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[sửa | sửa mã nguồn]

Nếu $s=\gamma (G_{1})\leq 4$ : 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 $s+1$ màu và suy ra: $\gamma (G)=s+1\leq 4+1=5$

Trường hợp 2[sửa | sửa mã nguồn]

Nếu $s=\gamma (G_{1})=5$ và $d_{G}(x_{0})\leq 4$ : 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: $\gamma (G)=5$

Trường hợp 3[sửa | sửa mã nguồn]

Nếu $s=\gamma (G_{1})=5$ và $d_{G}(x_{0})=5$ . 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[sửa | sửa mã nguồn]

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₄: $y_{4}\notin T(y_{1})$ .
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ì $v\notin T(y_{1})$ , còn nếu v tô bằng một trong hai màu này thì suy ra $v\in T(y_{1})$ .
Đỉ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 $y_{4}\in T(y_{1})$ 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 $y_{4}\notin T(y_{1})$ ): 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[sửa | sửa mã nguồn]

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.