Trích:
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]