Melyik az a legnagyobb X szám, melyre 8,8,7,5,4,4,3,2,1, X számsorozat realizálható egy egyszerű gráf fokszámsorozataként?

Szerencsésen kell szétbontani két csoportra a fokszámokat. Első körben tegyük csökkenő sorrendbe:

8;8;8;7;5;4;4;3;2;1

A következő a feladat:

Két csoportra bontjuk a fokszámokat, így a hozzájuk tartozó csúcsokat is. A "nagy" fokszámú csoportból a lehető legtöbb élt átirányítjuk a "kicsi" fokszámú csoportba, és ha szerencsések vagyunk, akkor a maradék élt már nem tudjuk behúzni a "nagy" csoport csúcsai között.

Próbálgatni kell, és egyszercsak kijön. Legyen a csoportosítás 8;8;8;7;5 és 4;4;3;2;1. A nagy csoportból a kicsibe így 4+4+3+2+1=14 él megy, a fokszámösszeg 8+8+8+7+5=36, ezzel 36-14=22-re csökken a "nagy" csoport fokszámösszege, de mivel csak ezek között húzunk be már csak élt, ezért 11 élt kell még behúznunk. A nagy csoportban 5 csúcs van, köztük 5*4/2=10 él húzható be, tehát 11 nem. Ezzel beláttuk, hogy egy szükséges (de nem elégséges) feltétel nem teljesül.

(A tétel szerint akárhogyan osztogatjuk ezeket a fokszámokat, mindig azt kapjuk, hogy a behúzandó élek száma mindig kevesebb vagy egyenlő a behúzható élek számával a "nagy" csoportban; ha ez nem igaz, akkor nincs ilyen gráf).