М250. а) Теорема Дирака о гамильтоновом цикле

При дворе короля Артура собрались n рыцарей. Некоторые из них враждуют, но у каждого рыцаря не менее n/2 друзей среди собравшихся. Докажите, что Мерлин — советник короля Артура — может усадить рыцарей за круглым столом так, чтобы рядом с каждым сидели его друзья. Это видео из альбома https://www.youtube.com/playlist?list=PL1JJ1jVZ9z5AiNJb0x5I087NFHSZnfPh2 Альбом «Задачник "Кванта"» https://www.youtube.com/playlist?list=PL1JJ1jVZ9z5BV88j2IxJQYRNJFSMrkNVC Условия и ссылки на решения: http://www.kvant.info/zkm_tex/zkm_main.pdf