Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.
19/24
Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.
Giải thích
Đồ thị G ở Hình 19 gồm 6 đỉnh, trong đó các đỉnh A, D, E có bậc 4, các đỉnh B, C có bậc 5 và đỉnh F có bậc 2 nên tổng bậc của hai đỉnh không kề nhau bất kì đều không nhỏ hơn 6. Do đó, theo định lí Ore, đồ thị G có ít nhất một chu trình Hamilton.