1761561
Định lý năm màu
https://vi.wikipedia.org/wiki?curid=1761561
Title: Đị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)."