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.
