Một câu lạc bộ có 99 thành viên, trong đó có một số cặp quen biết nhau (quan hệ quen biết có tính hai chiều). Giả sử số lượng người quen của mỗi thành viên trong câu lạc bộ đều từ 81 đến 90.

a) Chứng minh rằng tồn tại 2 thành viên của câu lạc bộ có ít nhất 67 người quen chung.

b) Chứng minh rằng tồn tại 10 thành viên của câu lạc bộ cùng quen chung một người và có số lượng người quen bằng nhau.

Coi mỗi thành viên là một đỉnh và nối hai đỉnh khi hai thành viên tương ứng quen nhau. Ta thu được một đồ thị vô hướng đơn có tập đỉnh $V$, $|V|=99$. Với $u\in V$, kí hiệu $N(u)$ là tập các đỉnh kề với $u$ và $d(u)=|N(u)|$. Theo giả thiết, $81\le d(u)\le 90$ với mọi $u\in V$.

a) Ta sẽ đếm các bộ $(w,\{u,v\})$, trong đó $u,v$ là hai đỉnh phân biệt cùng thuộc $N(w)$.
- Cố định $w$, ta có số bộ là $$\sum _{w\in V}{C}_{d(w)}^2\ge 99C_{81}^2.$$
- Mặt khác, với mỗi cặp $\{u,v\}$, số cách chọn $w$ chính là $|N(u)\cap N(v)|$.
Vì có $C_{99}^2$ cặp đỉnh nên tồn tại một cặp $\{u,v\}$ có số người quen chung ít nhất bằng
$$\frac{99C_{81}^2}{C_{99}^2}=\frac{81\cdot 80}{98}=66+\frac{6}{49}>66.$$
Số người quen chung là một số nguyên, do đó cặp này có ít nhất 67 người quen chung.

b) Giả sử ngược lại rằng không tồn tại 10 đỉnh có cùng bậc và có một đỉnh kề chung. Khi đó không thể có trường hợp mọi đỉnh đều có bậc 81, vì khi đó tổng các bậc bằng $99\cdot 81$ là một số lẻ, trái với bổ đề bắt tay. Do đó tồn tại một đỉnh $v$ có $d(v)>81$.
Với mỗi $k\in \{81,82,\dots ,89\}$, tập $N(v)$ chứa nhiều nhất 9 đỉnh bậc $k$; nếu không, ta có ngay 10 đỉnh cùng bậc $k$ và cùng kề với $v$. Vì
$$|N(v)|>81=9\cdot 9,$$
trong $N(v)$ phải có một đỉnh $w$ bậc 90.
Xét tập $N(w)$ gồm 90 đỉnh. Với mỗi $k\in \{81,82,\dots ,90\}$, tập này chứa nhiều nhất 9 đỉnh bậc $k$. Có đúng 10 giá trị có thể của $k$, nên $N(w)$ phải chứa đúng 9 đỉnh thuộc mỗi bậc $81,82,\dots ,90$. Đặc biệt, $N(w)$ chứa 9 đỉnh bậc 90. Cùng với $w$, ta được một tập $A$ gồm 10 đỉnh, tất cả đều có bậc 90.
Với mỗi $u\in A$, trong 99 đỉnh có đúng $99-90=9$ đỉnh không kề với $u$, kể cả $u$. Do đó có không quá $10\cdot 9=90$ đỉnh không kề với ít nhất một đỉnh của $A$. Vì thế có ít nhất $99-90=9$ đỉnh kề với mọi đỉnh của $A$ nên có 10 đỉnh của $A$ có cùng bậc và có đỉnh kề chung, mâu thuẫn với phản chứng.
Vậy tồn tại 10 thành viên có cùng số lượng người quen và cùng quen chung một người.