Giải Bài 2.21 trang 50 Chuyên đề Toán 11
Đề 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 6.
Lời giải
Phân tích bài toán. Giả sử trái lại, tồn tại một đơn đồ thị có đỉnh và cạnh, trong đó mỗi đỉnh có bậc hoặc bậc . Ta sẽ dẫn đến một điều mâu thuẫn.
a) Áp dụng định lí bắt tay (quan hệ giữa tổng bậc và số cạnh).
Gọi là số đỉnh có bậc và là số đỉnh có bậc . Vì đồ thị có đỉnh nên:
Theo định lí bắt tay, tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh:
Mặt khác, tổng các bậc tính theo là . Do đó:
b) Giải hệ và chỉ ra mâu thuẫn.
Từ suy ra . Thay vào phương trình :
Nhưng là số đỉnh nên phải là số nguyên không âm, trong khi không nguyên. Mâu thuẫn.
(Có thể thấy mâu thuẫn ngay cả khi không giải hệ: mỗi bậc hoặc đều chia hết cho , nên tổng các bậc phải chia hết cho ; thế nhưng không chia hết cho (vì không chia hết cho ). Lại mâu thuẫn.)
Kết luận. Điều giả sử là sai. Vậy không tồn tại đơn đồ thị nào có đỉnh và cạnh mà mọi đỉnh đều có bậc hoặc (đpcm).
Đáp số
Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.