Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton.
18/24
Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton.
Giải thích
Ta có: d(A) = 3, d(B) = 4, d(C) = 3, d(E) = 3, d(F) = 3. Đồ thị G ở Hình 17 gồm 5 đỉnh, mỗi đỉnh của đồ thị đều có bậc không nhỏ hơn 52. Do đó, theo định lí Dirac, đồ thị G có ít nhất một chu trình Hamilton.