Giải bài tập 2.11 trang 45 chuyên đề Toán 11 Kết nối

Điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n}{2}$ thì đồ thị G có một chu trình Hamilton.

Điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n-1}{2}$ thì đồ thị G có một đường đi Hamilton.

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 của đồ thị G không nhỏ hơn $\frac{n-1}{2}$ thì đồ thị sẽ chỉ có đường đi Hamilton.

Tuy nhiên ta có ví dụ:

Ta thấy bậc của mỗi đỉnh thỏa mãn điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n-1}{2}$.

Nhưng đồ thị trên có một chu trình Hamilton, ví dụ ABCFDEA. Do đó, đồ thị thỏa mãn điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n}{2}$.

Vậy đ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}$".