Giải luyện tập, vận dụng 10 trang 42 Chuyên đề Toán 11 Cánh diều

Luyện tập, vận dụng 10: Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton. 

Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton.


Đồ thị G gồm 5 đỉnh, mỗi đỉnh của đồ thị G có bậc lớn hơn $\frac{5}{2}$. Do đó, theo định lí Dirac, đồ thị có ít nhất một chu trình Hamilton. 


Bình luận

Giải bài tập những môn khác