Đị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 xoá đ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 BULLET 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 BULLET 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 BULLET T y không chứa y formula _ 25 BULLET Các đỉnh thuộc T y chỉ được tô bằng hai màu Green và White_BULLET_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 BULLET Đỉ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 BULLET Các đỉnh kề nhau trong T y thì đã hoán_vị màu BULLET 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 BULLET Indag_Math 13
Định_lý năm màu