Giải bài 2.11 trang 45

Đề 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ị G không nhỏ hơn $\frac{n}{2}$ 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 $\frac{n-1}{2}$”.

Lời giải chi tiết

Cho đơn đồ thị G có 5 đỉnh như hình vẽ sau:

Mỗi đỉnh của đồ thị này đều có bậc là 2 hoặc 3, đều không nhỏ hơn $\frac{5-1}{2}=2$, thỏa mãn điều kiện của định lí Dirac nếu thay điều kiện “bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n}{2}$” bằng điều kiện “bậc của mỗi đỉnh không nhỏ hơn $\frac{n-1}{2}$”.

Định lí Dirac là một điều kiện đủ cho sự tồn tại chu trình Hamilton, nhưng đồ thị trên lại không có chu trình Hamilton. Do vậy, đây vì ví dụ cần đưa ra để chứng tỏ rằng điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n}{2}$ 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 $\frac{n-1}{2}$”.