LUÔN CÓ CHU TRÌNH ĐƠN ĐỘ DÀI CHẴN

3, - BAI_02
BAI_02

3, luôn có chu trình đơn độ dài chẵn.

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

1

, x

2

, ... (y

1

) ... (y

2

) ... , x

k

> . Khi đó các đỉnh

y

1

,y

2

≠ x

2

kề với x

1

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

1

, ... ,y

1

] ,

[x

1

, ... , y

2

] , [x

1

, y

1

, ... , y

2

]. Nếu hai chu trình đầu có độ dài lẻ thì chu trình thứ ba

có độ dài chẵn.