84
84
Kategória: |
Bizonyítás
- Tétel
|
Évfolyam: |
9. |
Kulcsszó: |
Fagráfok |
Lektorálás: |
Nem lektorált |
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.