[namdung]

Nguyên văn bởi Mr Stoke

Bài 6 hệ quả trực tiếp từ định lý Bondy . Đầu tiên chọn ra 40 hs ta được 1 chu trình Hamiton. Chia 2 trường hợp: 2 hs còn lại quen nhau => xong. Nếu không quen thì 40 hs đó hợp hai hs thừa lập thành chu trình Hamiton.

Chỗ này không đơn giản như thế. Nếu chọn 40 học sinh chưa chắc đã có chu trình Hamilton. Phản ví dụ: Hai đồ thị $K_{21} $ rời nhau.

Bài này đúng là có liên quan đến các định lý Dirac, Ore, Bondy-Chvatal nhưng phải xem kỹ lại các chứng minh để xử lý việc "thiếu 1 chút".
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]