ĐỒ THỊ VÔ HƯỚNG VỚI N ĐỈNH (N ≥ 3), KHÔNG CÓ ĐỈNH NÚT VÀ BẬC CỦA MỖI ĐỈNHĐỀU KHÔNG NHỎ HƠN 2, LUÔN CÓ CHU TRÌNH ĐƠN

1) Đồ thị vô hướng với n đỉnh (n ≥ 3), không có đỉnh nút và bậc của mỗi đỉnh

đều không nhỏ hơn 2, luôn có chu trình đơn.

Xét đường đi đơn cực đại < x

, x

, ... (y) ... , x

> . Khi đó đỉnh y ≠ x

kề với x

phải nằm trên đường đi. Từ đó ta có một chu trình [x

, ... , y ].