Egy egyszerű gráf fokszámsorozata 1,2,3,5,6,7,8, x, x. A 3,4,5, értékek közül melyik (ek) lehetnek x helyén?

Van egy tétel, amely a következőt állítja: ha mohó algoritmussal kezded el megrajzolni a gráfot a fokszámsorozata alapján, akkor ki kell jönnie, vagy eleve nem lehetséges a fokszámsorozat.

Mohó algoritmus azt jelenti, hogy:

1. Felveszel annyi csúcsot, ahány eleme van a fokszámsorozatnak.

2. Veszed a legnagyobb fokszámú csúcsot (ha több van, közülük az egyiket), ez mondjuk legyen X fokszámú.

3. Összekötöd a csúcsot a további X legnagyobb fokszámú csúccsal.

4. Értelemszerűen minden behúzott él után 1-gyel csökkented az érintett csúcsok fokszámát.

5. Vissza a 2-es lépéshez, amíg el nem fogynak a fokszámok, vagy el nem akad az algoritmus.

Ha elakad az algoritmus (pl marad egy 3 fokú csúcs, de nincs mivel összekötni), akkor nem lehetséges a fokszámsorozat. A tétel ismerete nélkül ezt külön bizonyítanod kell az 1,2,3,...,x,x sorozatra, tehát ezen külön agyalni. De ha van megoldás, akkor a fenti algoritmus tuti megadja.