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

Giải Chuyên đề Toán 11 Kết nối tri thức Bài 8: Một vài khái niệm cơ bản

Luyện tập 4 trang 38 Chuyên đề Toán 11: 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.

Lời giải:

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 – x.

Tổng số bậc của các đỉnh là: 3x + 4(12 – x).

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

Do đó, ta có phương trình 3x + 4(12 – x) = 56, tức là 8 + x = 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.