A csúcsok és az élek közti összefüggés fagráfban

Bizonyítás

Tekintsünk egy csúcsú gráfot! Húzzunk be éleket! Minden egyes lépés után az összekötött éleket lehet már egy csúcsként kezelni, mert ha a csoporton belül összekötnénk bármelyik kettőt, akkor kört kapnánk, és így ez a gráf nem lenne fa. Így minden lépés után kapunk egy élt, és eggyel kevesebb csúcsot. Mivel csúcsunk van kezdetben, így lépés után már csak egyetlen csúcsunk lesz, tehát élt húztunk be. Tehát mindig eggyel több csúcs van, mint és a fagráfokban, így bebizonyítottuk a tételt.