Có chín người trong đó bất kì ba người nào cũng có hai người quen nhau. Chứng minh rằng tồn tại một nhóm bốn người đôi một quen nhau.

Coi mỗi người như một điểm, ta có chín điểm A, B, C,…

Nối hai điểm với nhau ta được một đoạn thẳng. Ta tô màu xanh nếu hai người không quen nhau, ta tô màu đỏ nếu hai người quen nhau. Ta sẽ chứng minh tồn tại một tứ giác có các cạnh và đường chéo cùng tô màu đỏ.

 Trường hợp có một điểm là đầu mút của bốn đoạn thẳng màu xanh AB, AC, AD, AE vẽ nét đứt (h.1.17)

Xét $\Delta ABC$ có hai đoạn thẳng AB, AC màu xanh nên đoạn thẳng BC màu đỏ vì bất kì tam giác nào cũng có một đoạn thẳng màu đỏ. Tương tự các đoạn thẳng CD, DE, EB, BD, CE cũng có màu đỏ (vẽ nét liền) (h.1.18). Do đó tứ giác BCDE có các cạnh và đường chéo được tô đỏ nghĩa là tồn tại một nhóm bốn người đôi một quen nhau.

- Trường hợp mọi điểm đều là đầu mút của nhiều nhất là ba đoạn thẳng màu xanh. Không thể mọi điểm đều là đầu mút của ba đoạn thẳng màu xanh vì khi đó số đoạn thẳng màu xanh là $\frac{9.3}{2}\notin N$.

Như vậy tồn tại một điểm là đầu mút của nhiều nhất là hai đoạn thẳng màu xanh, chẳng hạn đó là điểm A, do đó A là đầu mút của ít nhất là sáu đoạn thẳng màu đỏ, giả sử đó là AB, AC, AD, AE, AF, AG (h.1.19)

Trong sáu điểm B, C, D, E, F, G tồn tại ba điểm là đỉnh của một tam giác có ba cạnh cùng màu (đây là bài toán cơ bản về phương pháp tô màu) chẳng hạn đó là $\Delta BCD$ (h.1.20).

Trong $\Delta BCD$ có một cạnh màu đỏ (theo đề bài) nên ba cạnh của $\Delta BCD$ cùng màu đỏ. Khi đó tứ giác ABCD là tứ giác có các cạnh và đường chéo được tô đỏ, nghĩa là tồn tại một nhóm bốn người đôi một quen nhau.