Hány éle van egy 4 fából álló, 12 pontú erdőnek? (gráfokról beszélünk)

1. Ha az éleket úgy húzod be, hogy nem keletkezik kör, akkor 3 él behúzása után az erdő fává áll össze. Ennek a fának így 12 csúcsa van, azt pedig tudjuk, hogy egy fának mindig 1-gyel kevesebb éle van, mint ahány csúcsa, tehát 11 éle van. 3 él lett külön behúzva, így az eredeti erdőnek 8 éle volt.

2. Egy hatcsúcsú gráfnak legfeljebb 6*5/2=15 éle lehet. Ahhoz, hogy 12 élű legyen, 3 élt kell törölni. Azt kell megnézni, hogy hányféleképpen lehet törölni úgy, hogy "szerkezetileg" különbözzenek egymástól, és pontosan két darab 5-ös fokszám legyen.