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

Đị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.