Feladat: 4.13.
Van-e olyan egyszerű páros gráf, amelyben a csúcsok fokszáma rendre 3,3,3,3,3,4,4,5,6?
Megoldás: 4.13
Ha volna ilyen gráf, 9 csúcsa és 17 éle volna. Van hatodfokú pont, ezért az egyik osztályban legalább hat pont volna. Ha legalább hét volna ebben az osztályban, akkor az élszáma legfeljebb 14 lehetne. Tehát az egyik osztályban 6, a másikban 3 csúcs van és a két osztály között 17 él fut, tehát mindkét osztályban 17 a fokszámok összege. Ám a három legmagasabb fokú pontból is összesen 15 él indulhatna és ez ellentmondás.