2.25. Kiểm tra xem các điều kiện của định lí Ore có thỏa mãn với các đồ thị trên Hình 2.39 không.
Bài Làm:
Định lí Ore: Nếu G là đơn đồ thị có n đỉnh (n $\geq $ 3) và mỗi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn n thì G có một chu trình Hamilton.
Hình 2.39a có 5 đỉnh, các cặp đỉnh không kề nhau là B và D (tổng bậc hai đỉnh là 3 + 3 = 6 > 5); C và E (tổng bậc hai đỉnh là 3 + 3 = 6 > 5). Suy ra, đồ thị thỏa mãn với các điều kiện của định lí Ore.
Hình 2.39b có 5 đỉnh, các cặp đỉnh không kề nhau là M và Q (tổng bậc hai đỉnh là 2 + 2 = 4 < 5); M và P (tổng bậc hai đỉnh là 2 + 2 = 4 < 5); N và Q (tổng bậc hai đỉnh là 3 + 2 = 5); P và H (tổng bậc hai đỉnh là 2 + 3 = 5). Suy ra có cặp đỉnh M và Q, M và P không thỏa mãn điều kiện của định lí Ore.
