MỞ ĐẦU
Trước khi vào một hội nghị, các đại biểu bắt tay nhau (hai người bắt tay nhau nhiều nhất 1 lần). Có một đại biểu không bắt tay ai hết và thấy rằng có 4 người bắt tay 4 lần, 5 người bắt tay 5 lần và 6 người bắt tay 6 lần. Nếu hội nghị có đúng 16 đại biểu thì ông ta đã đếm nhầm. Vì sao có thể kết luận như vậy?
Bài Làm:
Vẽ một đồ thị với 16 đỉnh tương ứng với 16 đại biểu tham dự hội nghị.
Nếu hai đại biểu nào bắt tay nhau thì nối hai đỉnh tương ứng bằng một cạnh.
Theo đề bài, ta có một đồ thị 16 đỉnh, trong đó có 1 đỉnh bậc 0; 4 đỉnh bậc 4; 5 đỉnh bậc 5 và 6 đỉnh bậc 6.
Ta có 5 đỉnh bậc 5 mà theo hệ quả của định lí bắt tay: số đỉnh bậc lẻ của mọi đồ thị là một số chẵn.
Do đó mâu thuẫn với hệ quả. Suy ra đại biểu đó đã đếm sai.
