Matematyka.pl

Witam

Mam takie zadanko. Czy istnieje graf, który ma taki ciąg stopni wierzchołków \(\displaystyle{ (6, 6, 5, 5, 4, 4, 4, 4)}\), ale nie ma skojarzenia doskonałego?

Znalazłem na razie graf, który ma skojarzenie doskonałe.
Wydaję mi się, że nie ma takiego grafu o takim ciągu stopniu, który by go nie miał, ale nie wiem jak to udowodnić.

Z tw. Diraca ten graf ma cykl Hamiltona. Ten cykl ma parzystą długość, więc można wziąść z niego co drugą krawędź i mamy skojarzenie doskonałe. Nie istnieje graf bez skojarzenia doskonałego.