2.11. 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}$".
Bài Làm:
Đ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}$".
