CHƯƠNG VIIĐỒ THỊ PHẲNG VÀ TÔ MÀU ĐỒ THỊTừ xa xưa đã lưu truyền một bài toán cổ “Ba nhà, ba giếng”: Có ba nhà ở gần ba cái giếng, nhưng không có đường nối thẳng các nhà với nhau cũng như không có đường nối thẳng các giếng với nhau. Có lần bất hoà với nhau, họ tìm cách làm các đường khác đến giếng sao cho các đường nàyđôi một không giao nhau. Họ có thực hiện được ýđịnh đó không? Bài toán này có thể được mô hình bằng đồ thị phân đôi đầy đủ K3,3. Câu hỏi ban đầu có thể diễn đạt như sau: Có thể vẽ K3,3 trên một mặt phẳng sao cho không có hai cạnh nào cắt nhau? Trong chương này chúng ta sẽ nghiên cứu bài toán: có thể vẽ một đồ thị trên một mặt phẳng không có các cạnh nào cắt nhau không. Đặc biệt chúng ta sẽ trả...