Đề bài

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

Phương pháp giải

Trong đồ thị, một đường đi được gọi là đường đi Hamilton nếu đường đi đó đi qua tất cả các đinht của đồ thị, mỗi đỉnh đúng 1 lần.

Nếu chu trình là đường đi Hamilton thì chu trình đó được gọi là chu trình Hamilton.

Lời giải của GV Loigiaihay.com

Ta có: d(A) = 3, d(B) = 4, d(C) = 3, d(E) = 3, d(F) = 3. Đồ thị G ở Hình 17 gồm 5 đỉnh, mỗi đỉnh của đồ thị đều có bậc không nhỏ hơn \(\frac{5}{2}\). Do đó, theo định lí Dirac, đồ thị G có ít nhất một chu trình Hamilton.