Bài 4
Mười bảy người trao đổi thư từ với nhau, mỗi người với tất cả những người còn lại. Trong thư chỉ bàn về ba chủ đề khác nhau, và mỗi cặp người trao đổi chỉ bàn về một chủ đề. Chứng minh có ít nhất ba người viết cho nhau về cùng một chủ đề.
Bước 1 trên 5: Chứng minh bổ đề hai màu
Phân tích chi tiết
Trong đồ thị đầy đủ sáu đỉnh với hai màu cạnh, chọn một đỉnh. Ít nhất ba trong năm cạnh đi ra có cùng một màu, chẳng hạn đỏ, dẫn tới .