Az 1,2,3,4,5,6,7,8 pontokon a, hány fa adható meg b, hány egyszerű Graf adható meg?

a) Cayley tétele szerint 8^6=262.144

b) A 8 csúcsú gráfban (8*7)/2=28 él található. A kombinatorika szerint

0 élű gráf: (28 alatt 0)

1 élő gráf: (28 alatt az 1)

2 élő gráf: (28 alatt a 2)

.

.

.

28 élő gráf: (28 alatt a 28) készíthető, így összesen

(28 alatt a 0)+(28 alatt az 1)+(28 alatt a 2)+...+(28 alatt a 8) egyszerű gráf készíthető. Erről az összegről tudjuk a binomiális tétel szerint, hogy (1+1)^28=2^28-nal egyenlő, tehát 2^28-féle egyszerű gráf készíthető.