Đị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 γ ( G ) ≤ 5 {\displaystyle \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. 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. 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. Giả sử G = ( X , E ) {\displaystyle 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à: ∃ x ∈ X , d G ( x ) ≤ 5 {\displaystyle \exists x\in X,d_{G}(x)\leq 5} . Chứng minh Giả sử ngược lại: ∀ x ∈ X , d G ( x ) ≥ 6             ( α ) {\displaystyle \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 ≤ 2 {\displaystyle e\leq 2} thì điều phải chứng minh là hiển nhiên, ta chỉ xét e > 2 {\displaystyle e>2} . Áp dụng công thức bậc đỉnh số cạnh và d G ( x ) ≥ 6 , ∀ x ∈ X {\displaystyle d_{G}(x)\geq 6,\forall x\in X} : 6 n = ∑ x ∈ X 6 ≤ ∑ x ∈ X d G ( x ) = 2 e {\displaystyle 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 ≥ 3 n − 6 {\displaystyle e\geq 3n-6} Từ đó suy ra: 6 n ≤ 2 e ≤ 2 ( 3 n − 6 ) ⇒ 6 n ≤ 6 n − 12 ⇒ 0 ≤ − 12 ( ! ) {\displaystyle 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ử ( α ) {\displaystyle (\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. Giả sử G = ( X , E ) {\displaystyle 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à: ∃ x ∈ X , d G ( x ) ≤ 5 {\displaystyle \exists x\in X,d_{G}(x)\leq 5} 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 {\displaystyle 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 x0 mà d G ( x 0 ) ≤ 5. {\displaystyle d_{G}(x_{0})\leq 5.\,} 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ử s = γ ( G 1 ) ≤ 5 {\displaystyle s=\gamma (G_{1})\leq 5} 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: Nếu s = γ ( G 1 ) ≤ 4 {\displaystyle s=\gamma (G_{1})\leq 4} : 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 s + 1 {\displaystyle s+1} màu và suy ra: γ ( G ) = s + 1 ≤ 4 + 1 = 5 {\displaystyle \gamma (G)=s+1\leq 4+1=5} Nếu s = γ ( G 1 ) = 5 {\displaystyle s=\gamma (G_{1})=5} và d G ( x 0 ) ≤ 4 {\displaystyle d_{G}(x_{0})\leq 4} : 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: γ ( G ) = 5 {\displaystyle \gamma (G)=5} Nếu s = γ ( G 1 ) = 5 {\displaystyle s=\gamma (G_{1})=5} và d G ( x 0 ) = 5 {\displaystyle d_{G}(x_{0})=5} . 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). Nếu 5 đỉnh xung quanh x0 chưa dùng đủ 5 màu này: ta chỉ tô x0 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 x0 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 x0 được bố trí như hình ảnh. Ta xét hai dạng loại trừ nhau như sau: 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(y1) không chứa y4: y 4 ∉ T ( y 1 ) {\displaystyle y_{4}\notin T(y_{1})} . Các đỉnh thuộc T(y1) 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(y1) nếu v tô bằng màu khác với Green, White thì v ∉ T ( y 1 ) {\displaystyle 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 ∈ T ( y 1 ) {\displaystyle v\in T(y_{1})} . Đỉnh y4 không kề với bất kỳ đỉnh nào của T(y1) vì nếu ngược lại thì theo tính chất trên ta suy ra y 4 ∈ T ( y 1 ) {\displaystyle 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(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)): Các đỉnh kề nhau trong T(y1) thì đã hoán vị màu Các đỉnh kề với đỉnh của T(y1) mà không thuộc về T(y1) thì lại có màu khác với Green, White. 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 y 4 ∉ T ( y 1 ) {\displaystyle y_{4}\notin T(y_{1})} ): 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. 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. Đồ thị Định lý bốn màu Tô màu đồ thị ^ Trần Đan Thư - Dương Anh Đức (2008). Lý Thuyết Đồ Thị. Nhà xuất bản Đại học Quốc gia TP Hồ Chí Minh. *M., Aigner (1970), “Graph Theory - A Development from the 4-Color Problem”, BCS Associates, Moscow, Idaho USA R. Diestel (2000), Graph Theory, Springer_Verlag de Bruijn, N. G.; Erdős, P. (1951), “A colour problem for infinite graphs and a problem in the theory of relations” (PDF), Nederl. Akad. Wetensch. Proc. Ser. A, 54: 371–373 (= Indag. Math. 13)