Matematyka.pl

Jak pokazać, że nie istnieje graf o ciągu stopni wierzchołków \(\displaystyle{ (7,7,7,3,3,3,2,2)}\)?

Skorzystaj z algorytmu Havla-Hakimiego.

W treści zadania oczywiście chodziło o graf prosty.

Prościej na palcach - skoro wierzchołków jest osiem, a trzy z nich mają mieć stopień \(\displaystyle{ 7}\), to znaczy, że są połączone ze wszystkimi pozostałymi. Stąd wniosek, że wszystkie pozostałe musiałyby mieć stopień co najmniej \(\displaystyle{ 3}\).

Q.