Feladat: 10.15.
* Bizonyítsuk be, hogy páros sok olyan egyszerű gráf van, amelynek pontjai 1-től
n-ig vannak számozva, s amelyben nincs sem telített pont, sem izolált pont. Itt tehát nem egyszerűen pontokról, hanem
számozott pontokról van szó. Így
nem tekintjük azonosnak például
n=3-ra azt a két gráfot, amelyek közül az egyikben csak a kettes és a hármas nins összekötve, a másikban csak az egyes és a kettes nincs összekötve - bár ezek a gráfok a számozástól eltekintve izomorfak.
Megoldás: 10.15
Egy gráfban nem lehet egyszerre telített és izolált pont. Ha egy gráfban van telített pont, akkor a komplementerében van izolált pont és fordítva. Ha egyik sincs a gráfban, akkor a komplementerében sincs egyik sem. Tehát a sem telített, sem izolált pontot nem tartalmazó gráfokat párba állíthatjuk: mindegyiknek a komplementere lesz a párja. Minthogy
n legalább 2, a csúcsok számozottak, egyetlen gráfnak sem lehet önmaga a komplementere. Ezzel a feladat állítását beláttuk.