Feladat: 4.19.
Hány olyan nem-izomorf tízpontú összefüggő gráf van, amelyben van két-két negyed- és másodfokú pont van, a többi pont pedig elsőfokú?
 

Megoldás: 4.19
A fokszámok összege 18, tehát a gráfnak 9 éle van. Másrészt összefüggő, tehát fa. Elsőfokú pontok nem lehetnek egymással összekötve. Három eset van:

a) Ha a két negyedfokú pont össze van kötve. Ekkor a két másodfokú pont háromféle képpen helyezkedhet el: vagy mindkettő ugyanazzal a negyedfokú ponttal van összekötve, vagy egyik az egyikkel, másik a másikkal, végül lehet az is, hogy az egyik valamelyik negyedfokú ponttal és a másikkal van összekötve (ekkor a negyedfokú pontból indul ki egy háromélű út). Ez eddig három nem-izomorf gráf. (L. . ábrát!)

b) A két negyedfokú pont az egyik másodfokú ponton keresztül kapcsolódik egymáshoz, a másik másodfokú pont valamelyik negyedfokúval van összekötve. Ez egy további, az eddigeikkel nem izomorf gráf.

c) Végül lehet az is, hogy a két negyedfokú pont egy három élből álló úttal van összekötve, ez egy további, az eddigiekkel nem izomorf gráfot ad. (L. . ábrát!)

Összesen tehát öt, a feladatnak megfelelő nem-izomorf gráf van (mindegyik fa).