Feladat: 4.12.
Van-e olyan egyszerű páros gráf, amelyben a csúcsok fokszáma rendre 3,3,3,3,4,4,4,4?
Vagy bizonyítsuk be, hogy nincs ilyen, vagy adjuk meg az összeset!
Megoldás: 4.12
Ilyen gráfot kapunk, ha egy
K4,4
-ből elhagyunk két, közös pont nélküli (független) élt. Több nincs. Ugyanis az ilyen gráf élszáma 14, tehát mindkét csoportból 14 élnek kell kiindulnia. Vagyis mindkét csoportban 14 a fokszámok összege, ami csak úgy lehet, hogy mindkét csoportban két-két negyed- és harmadfokú pont van. A negyedfokú pontok a másik csoport minden pontjával össze vannak kötve, a harmadfokúak eggyel-eggyel nincsenek összekötve, s nem lehetnek ugyanazzal az
x ponttal nem összekötve, mert akkor
x legfeljebb másodfokú lehetne.