KITÉRŐ A VÉGTELEN GRÁFOKRÓL
Megmutatjuk, hogy az állítás végtelen gráfokra nem igaz. Van ugyanis olyan végtelen egyszerű gráf, amelyben minden pont fokszáma különböző. Legyenek a gráf pontjai az 1, 2, 3, 4, … pozitív egész számok. Olyan gráfot akarunk csinálni, amelyben az i-edik csúcspont fokszáma éppen i. Minden pontra ráírjuk tehát a sorszámát, hogy tudjuk: ekkorára akarjuk a fokszámát. Ezután először összekötjük az 1-es pontot a 2-es ponttal. Ezzel az 1-es pont fokszáma megfelelő lett, őt tehát kihúzzuk és a 2-esre most 1-et írunk: még ennyi „hiányzik a fokszámából”, a többi pontra írt szám változatlan marad. Ezután sorra vesszük a 2-es pontot, ezt további 1 ponttal kell összekötnünk, összekötjük a 3-as ponttal. Elhagyjuk a 2-es pontot, hiszen most már az ő fokszáma is megfelelő és a 3-as pontra eggyel kevesebbet írunk. Most sorra vesszük a 3-as pontot, ezen jelenleg 2-es szám áll, ennyi élt kell még belőle behúznunk: összekötjük a 4-es és 5-ös ponttal, majd az ezekre írt számot csökkentjük eggyel és elhagyjuk a 3-as pontot. Így minden lépésben sorra vesszük a következő pontot, ha a pillanatnyilag rajta szereplő szám i, akkor összekötjük i olyan ponttal, amelyen jelenleg pozitív szám áll. Ezután ezt a pontot elhagyhatjuk, és a vele most összekötött pontokra írt számot eggyel csökkentjük. (Ha i=0 volt, akkor e szerint az eljárás szerint egyszerűen elhagyjuk a pontot, mert már „rendben van”.) Ezt az eljárást minden egyes pontra elvégezve egy olyan gráfhoz jutunk, amelyben az i-edik pont fokszáma pontosan i. (Az ábrán azt az állapotot rajzoltuk fel, amikor az első négy pont fokszáma már „rendben van”, az 5-ös pontból a 6-osba, 7-esbe és 8-asba kell majd berajzolni élt.)
