Rajzoljunk egy olyan 5 csúcsú egyszerű gráfot, aminek 2 harmadfokú és 2 negyedfokú csúcsa van. Hány ilyan gráf van ha a csúcsokat nem számozzuk meg és ha megszámozzuk?

Érdemesebb a komplementereket megszámolni; a keresett gráfok komplementereiben két csúcs fokszáma 1, két csúcsé pedig 0. Innentől kezdve nincs sok variációs lehetőség; vagy a két egyest kötöd össze egymással, vagy mindkét egyest az utolsó csúccsal, amiről nem tudunk semmit. Tehát kétféle lehetőség van, hogyha a csú sokat nem számozzuk.

Ha számozzuk a csúcsokat, akkor csak a fokszámokat kell ismétlésesen permutálnunk;

-ha a (komplementer) gráfban 1 él van, a csúcsok fokszámai: 0;0;0;1;1, itt a lehetőségek száma 5!/(3!*2!)=10

-ha a gráfban két él van, akkor a fokszámok: 0;0;1;1;2, itt a lehetőségek száma 5!/(2!*2!)=30

Összesen tehát 10+30=40 gráf létezik számozott csúcsokkal.

Minden gráfelméleti ismeret nélkül:

A negyedfokúak az összes többi csúccsal össze vannak kötve. A harmadfokúak 1-1 csúccsal nincsenek. Ha ez úgy valósulna meg, hogy a harmadfokúak között levő él hiányozna, akkor az ötödik csúcs a negyed és harmadfokúakkal is össze lenne kötve, azaz negyedfokú lenne. Ez nem jó megoldás.

Az megmaradó egyetlen megoldás az, hogy az ötödik csúcs nincs összekötve a harmadfokúakkal. (És másodfokú.)

Ha a csúcsok számozva vannak, akkor ki kell választanunk a másodfokút. 5 lehetőség. És a megmaradt 4-ből 2 harmadfokút 4*3/2=6. Összesen 30.

Élek összesen: (2*4+2*3+2)/2=8.