Bài 6
Cho một tập hữu hạn các điểm trên mặt phẳng, mỗi điểm có tọa độ nguyên. Có phải luôn có thể tô các điểm đỏ hoặc trắng sao cho với mọi đường thẳng song song với một trong hai trục tọa độ, trị tuyệt đối của hiệu giữa số điểm trắng và số điểm đỏ trên không vượt quá ?
Bước 1 trên 4: Dựng đồ thị hai phía
Hiểu nôm na
Một điểm tự nhiên được xem như một cạnh: hàng và cột của nó là hai đầu mút. Cân bằng màu trên các đường song song trục trở thành cân bằng màu các cạnh kề mỗi đỉnh.
Mỗi đường ngang chứa điểm cho một đỉnh, mỗi đường dọc chứa điểm cho một đỉnh khác. Điểm trở thành cạnh nối đỉnh hàng với đỉnh cột . Đồ thị là hai phía; tô cạnh đỏ hoặc trắng chính là tô điểm, và điều kiện trên mỗi đường là điều kiện tại đỉnh.