Rysowanie grafu mając ciąg stopni wierzchołków

[librusss]

Zadanie wydaje się proste, jednak nie wiem jak narysować (lub wykazać, że to niemożliwe) graf o ciągu stopni wierzchołków: (0, 1, 2, 3, 4). Raczej nie będzie możliwe narysowanie go. Nie wiem jednak jak to wykazać.

Na logikę: z lematu o podawaniu rąk, mamy, że E - ilość krawędzi = 5. Jednak łącząc pierwszy wierzchołek z czterema innymi, mamy już "zużyte" 4 krawędzie. Została więc jedna "dostępna" krawędź, a nie damy radę połączyć nią wierzchołków w ten sposób by miały one wymagane stopnie.

[kerajs]

Lemat o którym wspominasz jest spełniony, gdyż suma stopni jest parzysta, podobnie jak ilość wierzchołków nieparzystego stopnia.

Stopień 0 jednego z wierzchołków oznacza, iż graf nie jest spójny, a stopień 4 innego wierzchołka tę spójność wymusza, więc graf pięciowierzchołkowy o podanych powyżej stopniach nie istnieje.