Đề bài

Chứng minh rằng không có đơn đồ thị với 12 đỉnh và 28 cạnh mà các đỉnh đều có bậc 3 hoặc 4.

Phương pháp giải

Trong một đồ thị, tổng tất cả bậc của đỉnh là một số chẵn và bằng hai lần số cạnh của đồ thị

Lời giải của GV Loigiaihay.com

Giả sử có đồ thị thỏa mãn yêu cầu bài toán. Gọi x là số đỉnh bậc 3 của đồ thị.

Khi đó, ta có số đỉnh bậc 4 là: \(12{\rm{ }}-{\rm{ }}x.\)

Tổng số bậc của các đỉnh là: \(3x{\rm{ }} + {\rm{ }}4\left( {12{\rm{ }}-{\rm{ }}x} \right).\)

Vì đồ thị có 28 cạnh nên theo Định lí bắt tay thì đồ thị có tổng số bậc là \(28{\rm{ }}.{\rm{ }}2{\rm{ }} = {\rm{ }}56.\)

Do đó, ta có phương trình \(3x{\rm{ }} + {\rm{ }}4\left( {12{\rm{ }}-{\rm{ }}x} \right){\rm{ }} = {\rm{ }}56\), tức là \(8{\rm{ }} + {\rm{ }}x{\rm{ }} = {\rm{ }}0\). Phương trình này không có nghiệm là số tự nhiên, do đó không tồn tại đồ thị thỏa mãn điều kiện đề bài.