Egy 6 csúcsú gráf fokszámai 2,2,3,3,5,5 hány ilyen gráf van ha megszámozzuk és ha nem? Plusz az élek száma.

1 ha nem számozzuk.

90 ha megszámozzuk.

10 él.

Rajzolj!

fokszám: ahány él fut be

fokszámok összege: 20 és egy él két pontba fut be, így 2-t ad bele a fokszámba, tehát a fokszámok (mindig páros) fele az élek száma.

6 pont van. és két 5 fokszámú, ami azt jelenti, hogy 2 pont minden ponttal össze van kötve. De ez azt is jelenti hogy a maradék 4 pont 2 ponttal minimum össze van kötve, így legalább 2 fokszámúak. 2 ilyenből kell is, végül a másik kettőt összekötjük egymással, hogy 3 legyen a fokszámuk. Latható, hogy ha a pontokat nem különböztetjük meg csak 1 féle képpen lehet.

Ha a pontok különbözőek, akkor 6 alatt a 2 azaz 15 féleképpen választhatjuk meg a 2 db 5 fokszámú pontot. A maradék 4 közül meg 4 alatt a 2 azaz 6 féle képpen választhatjuk meg a 2 db 3 fokszámú pontokat. Tehát 15*6=90