Matematické Fórum

Dobrý den potřeboval bych poradit s timto příkladem. Jestli by někdo veděl tak napište děkuji.

Na večírku je 25 lidí. Každá dvojice zná dohromady všech ostatních 23 lidí. Lze tyto lidi rozesadit kolem kulatého stolu tak, že každý sedí mezi svými známými? POZOR! Zde chápeme relaci "býti známý s" jako symetrickou relaci, tedy zná-li se x s y, tak y se zná s x.
Návod: Ke každé takové situaci umíte sestavit graf, kde vrcholy jsou jednotliví lidé na večírku a hrana mezi vrcholy x a y je přesně tehdy, když x zná y. Máte ukázat, že každý takový graf obsahuje cyklus, který prochází všemi vrcholy grafu.