Giải Bài 2.11 trang 45 Chuyên đề Toán 11
Đề bài
Hãy chỉ ra một ví dụ chứng tỏ rằng điều kiện bậc của mỗi đỉnh của đồ thị không nhỏ hơn trong Định lí Dirac, không thể thay bằng điều kiện "bậc của mỗi đỉnh không nhỏ hơn ".
Lời giải
Nhắc lại Định lí Dirac (SGK). Cho đồ thị có đỉnh (). Nếu bậc của mỗi đỉnh của đều không nhỏ hơn thì có chu trình Hamilton.
Ta phải chỉ ra một đồ thị trong đó bậc của mỗi đỉnh đều không nhỏ hơn nhưng đồ thị không có chu trình Hamilton. Khi đó điều kiện không thể hạ xuống thành .
Xây dựng ví dụ (). Xét đồ thị gồm hai tam giác (hai đồ thị đầy đủ ) có chung đúng một đỉnh :
- Tam giác thứ nhất: với các cạnh ;
- Tam giác thứ hai: với các cạnh .
Đồ thị có đỉnh nên và .
Kiểm tra bậc của các đỉnh.
- (nối với );
- .
Vậy mọi đỉnh đều có bậc , tức là thỏa mãn điều kiện "bậc mỗi đỉnh không nhỏ hơn ".
(Lưu ý: , mà nên không thỏa mãn điều kiện Dirac — đúng như mong muốn.)
Chứng tỏ không có chu trình Hamilton. Khi bỏ đỉnh (cùng các cạnh nối với nó), đồ thị tách thành hai phần rời nhau là và ; như vậy là đỉnh cắt. Một chu trình Hamilton phải đi qua đủ cả bốn đỉnh . Nhưng mọi đường nối từ nhóm sang nhóm đều bắt buộc đi qua , trong khi một chu trình chỉ được đi qua đúng một lần. Do đó không thể vừa nối vừa chuyển sang rồi quay về khép kín — nghĩa là không có chu trình Hamilton.
Kết luận. Đồ thị ở trên có bậc mỗi đỉnh nhưng không có chu trình Hamilton. Vậy trong Định lí Dirac, điều kiện bậc mỗi đỉnh không nhỏ hơn không thể thay bằng điều kiện bậc mỗi đỉnh không nhỏ hơn (đ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.