Gráfok fa, erdő gráf segít valaki ebben a feladatban?

Első körben rajzolsz egy ilyen erdőt; példának okáért rajzolj egy 16 élű fát, és ezt a gráfot pakold körbe 4 izolált ponttal. Ennek tudjuk, hogy 17+1+1+1+1=21 csúcsa van. Ebből megsejtjük, hogy ez a megoldás.

Bizonyítás: Vegyünk egy 21 csúcsú fát, ennek ugye 20 éle van. Ebből a fából 5 komponensű erdőt úgy tudunk gyártani, hogy törlünk belőle 4 élt (minden törlésnél +1 komponenst nyerünk, mivel tetszőleges fából 1 csúcsot törölve a gráf 2 komponensre esik szét (a minimális összefüggőség miatt), és az így nyert komponens is biztosan fa lesz). Ha ebből törlünk 4 élt, akkor 16 él marad, és egy 5-fás erdő. Ezzel a csúcsok száma nem változik, tehát 21 csúcsa van.

Egy N csúcsú fában N-1 él van.

Vagyis ha a csúcsok számából kivonjuk az élek számát, 1-et kapunk. Ezért egy erdő esetében ha a csúcsok számából kivonjuk az élek számát, megkapjuk, hány fa van az erdőben!

Most:

N - 16 = 5

N = 21