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

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

Ta có lí thuyết: Giả sử G là đồ thị đơn gồm n đỉnh và m cạnh. Nếu m $\geq $ $\frac{n^{2}-3n+6}{2}$ thì G là đồ thị có chu trình Hamilton.

Áp dụng vào bài toán ta được điều phải chứng minh.

b) Ta có đồ thị sau có 5 đỉnh, 7 cạnh và đồ thị không có chu trình Hamilton.