Megoldás. Mivel minden $i\le n$-re $i$ darab $i$-edfokú csúcs van, a gráf csúcsainak $S$ fokszám összege ${\sum }_{i=1}^n{i}^2$; ez nyilván páros, hiszen éppen az élek számának kétszerese. Az $i^2$ paritása megegyezik az $i$ paritásával, tehát $S$ paritása megegyezik a ${\sum }_{i=1}^{n}i$ paritásával, ami $\frac{n\left(n+1\right)}{2}$, ezért szükséges, hogy az egymáshoz relatív prím $n$ és $n+1$ tényezők valamelyike 4-gyel osztható legyen, vagyis az $n$ szám 4-gyel osztva 0 vagy 3 maradékot adjon. Megmutatjuk, hogy ez a feltétel egyben elégséges is. A szóbajövő legkisebb $n=3$, illetve $n=4$ esetben ilyen gráfot láthatunk a mellékelt ábrán. Ezután elegendő megmutatni, hogy ha valamely $n$-re találtunk egy megfelelő $G_n$ gráfot, akkor $n$ értékét 4-gyel növelve, konstruálni tudunk egy megfelelő $G_{n+4}$ gráfot is. Ezt úgy tehetjük meg, hogy a $G_n$ gráf mellé felvesszük a $K_{n+1}$, $K_{n+2}$, $K_{n+3}$ és $K_{n+4}$ teljes gráfokat rendre $n+1$, $n+2$, $n+3$, illetve $n+4$ csúcson úgy, hogy az öt gráf csúcshalmazai páronként diszjunktak legyenek, majd pedig a $K_{n+1}$ és $K_{n+4}$ gráfok összesen $2n+5$ csúcsát egy-egy új él segítségével összepárosítjuk a $K_{n+2}$ és $K_{n+3}$ gráfok összesen $2n+5$ csúcsával. (Tulajdonképpen már a $G_4$ gráfot is megkaphatjuk ilyen módon a 0 szögpontú $G_0$ üres gráfból.) Ezzel a $G_n$-hez tartozó csúcsok fokszáma nem változik; a $K_{n+1}$, $K_{n+2}$, $K_{n+3}$ és $K_{n+4}$ gráfok csúcsainak foka eredetileg rendre $n$, $n+1$, $n+2$ és $n+3$, a párosítások révén ezek a fokszámok 1-gyel nőnek, tehát az új gráf az $n+1$, $n+2$, $n+3$, $n+4$ fokokra is teljesíti a feladat feltételét, $\left(n+4\right)$-nél magasabb fokú pontot pedig nem tartalmaz.