Chứng minh: Không mất tính chất tổng quát có thể giả sử G liên thông. Cố định đỉnh u của G và tô nó bằng màu 0 trong hai màu 0 và 1. | CHƯƠNG VII ĐÒ THỊ PHẲNG VÀ TÔ MÀU ĐỒ THỊ Chứng minh Không mất tính chất tổng quát có thể giả sử G liên thông. Cố định đỉnh u của G và tô nó bằng màu 0 trong hai màu 0 và 1. Với mỗi đỉnh v của G tồn tại một đường đi từ u đến v nếu đường này có độ dài chẵn thì tô màu 0 cho v nếu đường này có độ dài lẻ thì tô màu 1 cho v. Nếu có hai đường đi mang tính chẵn lẻ khác nhau cùng nối u với v thì dễ thấy rằng G phải chứa ít nhất một chu trình độ dài lẻ. Điều mâu thuẫn này cho biết hai màu 0 và 1 tô đúng đồ thị G. . Mệnh đề Với mỗi số nguyên dương n tồn tại một đồ thị không chứa K3 và có sắc số bằng n. Chứng minh Ta chứng minh mệnh đề bằng quy nạp theo n. Trường hợp n 1 là hiển nhiên. Giả sử ta có đồ thị Gn với kn đỉnh không chứa K3 và có sắc số là n. Ta xây dựng đồ thị Gn 1 gồm n bản sao của Gn và thêm knn đỉnh mới theo cách sau mỗi bộ thứ tự v1 v2 . vn với vi thuộc bản sao Gn thứ i sẽ tương ứng với một đỉnh mới đỉnh mới này được nối bằng n cạnh mới đến các đỉnh v1 v2 . vn. Dễ thấy rằng Gn 1 không chứa K3 và có sắc số là n 1. . Định lý Định lý 5 màu của Kempe-Heawood Mọi đồ thị phẳng đều có thể tô đúng bằng 5 màu. 104 Chứng minh Cho G là một đồ thị phẳng. Không mất tính chất tổng quát có thể xem G là liên thông và có số đỉnh n 5. Ta chứng minh G được tô đúng bởi 5 màu bằng quy nạp theo n. Trường hợp n 5 là hiển nhiên. Giả sử định lý đúng cho tất cả các đồ thị phẳng có số đỉnh nhỏ hơn n. Xét G là đồ thị phẳng liên thông có n đỉnh. Theo Hệ quả trong G tồn tại đỉnh a với deg a 5. Xoá đỉnh a và các cạnh liên thuộc với nó ta nhận được đồ thị phẳng G có n-1 đỉnh. Theo giả thiết quy nạp có thể tô đúng các đỉnh của G bằng 5 màu. Sau khi tô đúng G rồi ta tìm cách tô đỉnh a bằng một màu khác với màu của các đỉnh kề nó nhưng vẫn là một trong 5 màu đã dùng. Điều này luôn thực hiện được khi deg a 5 hoặc khi deg a 5 nhưng 5 đỉnh kề a đã được tô bằng 4 màu trở xuống. Chỉ còn phải xét trường hợp deg a 5 mà 5 đỉnh kề a là b c d e f đã được tô bằng 5 màu rồi. Khi đó trong 5 .
