Feladat: 2.15.
Igaz-e a következő állítás:
Legyen G egyszerű véges gráf. G minden pontjának a fokszáma ugyanolyan paritású, mint G‾-beli foka. Jelölve: minden x∈V(G)-re dG(x)=dG‾(x).
Megoldás: 2.15
Mivel dG‾=n-1-dG(x), ahol nG pontszámát jelöli, ezért az állítás pontosan akkor igaz, ha G pontszáma páratlan.