Matematyka.pl

Zadanie: czy istnieje graf nieskierowany o następujących stopniach wierzchołków:
1, 1, 3, 3, 3, 4, 6, 7?

Próbuję narysować taki graf:
- wierzchołek o stopniu 7 łączę ze wszystkimi pozostałymi, mam więc jeden o stopniu 7 i siedem o stopniu 1
- wybieram jeden z wierzchołków o stopniu jeden i łączę z pięcioma innymi o stopniu 1: mam teraz jeden o stopniu 7, jeden o stopniu 6, pięć o stopniu 2 i tylko jeden o stopniu 1 (czyli już na tym etapie brakuje mi drugiego wierzchołka o stopniu 1)
Wnioskuję, że taki graf nie istnieje.

Pytanie jest takie: czy istnieje jakiś formalny warunek na stopnie wierzchołków, który w tym przypadku nie jest spełniony?

Podbijam. Domyślam się że warunek, że suma stopni ma być parzysta to za mało?

Zdecydowanie za mało, bo w tym przypadku jest spełniony.

Huub900, W pierwszym poście prawie udowodniłeś, że taki graf nie istnieje. Można to ubrać w trochę bardziej matematyczne narzędzia (zasada szufladkowa Dirichleta).