Tài liệu đồ 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ả
lời bài toán ba nhà ba giếng. Thường có nhiều cách biểu diễn đồ thị. Khi nào có thể tìm
được ít nhất một cách biểu diễn đồ thị không có cạnh cắt nhau?