Bài 3
Cho S là một tập gồm 2004 điểm trên mặt phẳng, không có ba điểm thẳng hàng, và L là tập mọi đường thẳng xác định bởi từng cặp điểm của S. Một đường thẳng ngăn cách hai điểm nếu chúng nằm ở hai phía đối nhau và không điểm nào nằm trên đường thẳng đó. Chứng minh rằng có thể tô S bằng không quá hai màu sao cho hai điểm cùng màu khi và chỉ khi có một số lẻ đường thẳng trong L ngăn cách chúng.
Bước 5 trên 5: Kết luận tính chất của cách tô
Phân tích chi tiết
Bước trước cho biết n(p,q)+n(p,r)+n(q,r) lẻ. Do đó n(q,r) lẻ khi và chỉ khi n(p,q), n(p,r) cùng tính chẵn lẻ, đúng bằng khi q,r cùng màu. Cách tô chỉ dùng hai màu xanh và đỏ.