Bài toán 1. Cho $G$ là một graph đơn, ở đây $\left |V \right |=n;\, \left | E \right |=e$. Chứng minh rằng $$e\leq \frac{n\left ( n-1 \right )}{2}$$
Lời giải.
Gọi các đỉnh của của graph là $A_{1},\,A_{2},\,...,\,A_{n}$
Với mỗi đỉnh $A_{i}$ ta có nhiều nhất $n-1$ cạnh nối đỉnh $A_{i}$ và $A_{j}$ (với $i\neq j$)
Do đó với $n$ đỉnh của graph thì có nhiều nhất $n(n-1)$ cạnh.
Nhưng cạnh $\left ( A_{i};A_{j} \right )$ được lặp lại $2$ lần nên ta có $$e\leq \frac{n\left ( n-1 \right )}{2}$$
Bài toán 2. Có $605$ người trong một dạ hội. Giả sử rằng mỗi người bắt tay với ít nhất một
người khác. Chứng minh rằng phải có một người bắt tay với ít nhất $2$ người khác.
Lời giải.
Giả sử không có ai bắt tay với $2$ người trở lên.
Theo giả thiết đề bài, mỗi người chỉ bắt tay với $1$ người khác.
Ta sẽ xây dựng graph như sau: mỗi người tương ứng một đỉnh của graph, nếu hai người $A_{i}$
và $A_{j}$bắt tay nhau thì biểu diễn bằng cạnh $\left ( A_{i};A_{j} \right )$
Do mỗi người chỉ được bắt tay với $1$ người khác nên từ mỗi đỉnh chỉ có $1$ cạnh xuất phát từ
điểm đó.
Nếu $e\geq 303$ thì số đình ít nhất là $606$ (điều này vô lý vì chỉ có $605$ người)
Nếu $e\leq 302$ thì số đỉnh nhiểu nhất là $604$ (vô lý)
Vậy điều giả sử vô lý.
Do đó tồn tại một người bắt tay với ít nhất $2$ người khác.
Tổng quát. Có $n$ ($n$ lẻ) người trong một dạ hội. Giả sử rằng mỗi người bắt tay với ít nhất một
người khác. Chứng minh rằng phải có một người bắt tay với ít nhất $2$ người khác.
Bài toán 3. (USA MO 1978)
Có $9$ nhà toán học gặp nhau tại $1$ hội nghị toán học. Với bất kì $3$ người, có ít nhất $2$ người
trong đó nói cùng $1$ ngôn ngữ. Nếu biết mỗi nhà toán học chỉ có thể nói nhiều nhất $3$ ngôn
ngữ. Chứng minh rằng có ít nhất $3$ nhà toán học có thể cùng nói $1$ ngôn ngữ.
Lời giải.
Ta xây dựng graph như sau: Mỗi người tương ứng với một đỉnh của graph, nếu hai người
cùng nói với nhau bằng ngôn ngữ $i$ thì ta nối $2$ đỉnh đó bằng $1$ cạnh và tô màu $i$.
Gọi $v_{1},v_{2},...,v_{9}$ là các đỉnh tương ứng với $9$ người.
*
Nhận xét. Nếu $\left ( v_{1};v_{2} \right )$ và $\left ( v_{1};v_{3} \right )$ được tô cùng màu $i$ thì $\left ( v_{2};v_{3} \right )$ cũng được tô màu $i$.
Trường hợp 1. Nếu $v_{1}$ nói được với $8$ người còn lại. Mà $v_{1}$ thì có thể nói $3$ thứ tiếng nên theo
nguyên lí Đirichlet, tồn tại $2$ người trong $8$ người đó nói cùng ngôn ngữ với $v_{1}$
Trường hợp 2. Nếu $v_{1}$ không nói được với ít nhất một người. Giả sử ngưới đó là $v_{2}$
Xét bộ $\left ( v_{1};v_{2};v_i \right ),\, i=\overline{3,9}$, ta được $v_{i}$ nói được với $v_{1}$ hoặc $v_{2}$
Theo nguyên lý Đirichlet thì tồn tại một người ($v_{1}$ hoặc $v_{2}$) nói được với ít nhất $4$ người. Giả sử là $v_{1}$
Theo nguyên lý Đirichlet thì tồn tại $\left ( v_{1};v_{i} \right )$ và $\left ( v_{1};v_{j} \right )$ được tô cùng màu.
Theo nhận xét thì $v_{1}$, $v_{i}$ và $v_{j}$ nói cùng ngôn ngữ.
Vậy phải có ít nhất $3$ nhà toán học có thể cùng nói $1$ ngôn ngữ.
Bài toán 4. Có $n$ hộp thuốc. Bất kỳ $2$ hộp thuốc có cùng $1$ loại thuốc ở bên trong
và mỗi loại thuốc được chứa trong đúng $2$ hộp thuốc. Hỏi có bao nhiêu loại thuốc tất cả $?$
Lời giải.
Ta xây dựng một graph như sau:
- Mỗi đỉnh tương ứng với một hộp thuốc. Gọi các đỉnh là $v_{1},v_{2},...,v_{n}$
- Nếu loại thuốc $k$ nằm trong hộp $v_{i},v_{j}$ thì được biểu diễn bằng cạnh $(v_{i};v_{j})$ có màu $k$
Dễ thấy đây là một graph đầy đủ (vì bất kỳ 2 hộp thuốc luôn có chung $1$ loại thuốc)
Các cạnh có màu khác nhau (vì nếu $2$ cạnh được tô cùng màu thì tồn tại ít nhất $3$ hôp chứa
cùng $1$ loại thuốc, điểu này vô lý với giả thiết)
Do đó số loại thuốc chính là số cạnh của graph. Vậy số loại thuốc là $$\frac{n(n-1)}{2}$$
Bài toán 5. Có $n> 3$ người. Một vài người trong đó biết nhau và các người khác không
biết nhau. Có ít nhất $1$ người không biết các người khác. Hỏi số lớn nhất các cặp biết nhau.
Lời giải.
Ta xây dựng graph như sau:
- Mỗi người tương ứng một đỉnh của graph. Gọi các đỉnh là $v_{1},v_{2},...,v_{n}$
- Nếu $2$ người $v_{i}$ và $v_{j}$ biết nhau thì biểu diễn bằng cạnh $\left ( v_{i},v_{j} \right )$
Do vai trò như nhau nên giả sử $v_{n}$ không biết các người khác.
Để số cặp biết nhau lớn nhất thì $n-1$ đỉnh còn lại tạo thành một graph đầy đủ.
Dẫn đến số cạnh biết nhau lớn nhất là $$\frac{(n-1)(n-2)}{2}$$
Bài toán 6. Có $18$ đội tuyển trong $1$ giải đấu. Ở mỗi vòng, nếu một đội tuyển thi đấu với
một đội tuyển khác thì nó sẽ không thi đấu với cùng đội tuyển đó ở vòng đấu khác. Hiện nay
đã thi đấu $8$ vòng. Chứng minh rằng phải có $3$ đội tuyển chưa thi đấu với nhau trong $8$ vòng
đấu đó.
Lời giải.
Gọi các đội tuyển là $v_{1},v_{2},...,v_{18}$
Giả sử không tồn tại $3$ đội tuyển nào mà chưa thi đấu với nhau đôi một.
Do vai trò của các $v_{i}$ như nhau nên giả sử $v_{1}$ thi đấu với $v_{2},v_{3},...,v_{9}$ trong $8$ vòng.
Nếu tồn tại $2$ đội trong $v_{10},v_{11},...,v_{18}$ chưa thi đấu với nhau, giả sử $2$ đội đó là $v_{i}$ và $v_{j}$
Khi đó bộ ba đội $(v_{1},v_{i},v_{j}$ chưa thi đấu với nhau đôi một .
Do đó $9$ đội $v_{10},v_{11},..,v_{18}$ thi đấu đôi một với nhau. Mà hiện nay đã thi đấu $8$ vòng nên $9$
đội này thi đấu nội bộ với nhau.
Điều này vô lý vì trong một vòng đấu $9$ đội sẽ có $1$ đội không thi đấu.
