Feladat: 3.6.
Mutassuk meg, hogy ha egy 4-reguláris gráfban bármely pont szomszédai között két független él a komplementerben fut, akkor a gráfban nincs négypontú teljes részgráf.
Megoldás: 3.6
Tegyük fel, hogy van négypontú teljes részgráf és legyen egyik pontja
x. A másik három pont csak
x szomszédai közül kerülhet ki. Legyenek a szomszédai
y,z,u,v. A feladat feltétele szerint hiányzik például az
yz és az
uv él. Ezért
y és
z közül legfeljebb az egyik szerepelhet a teljes négyesben, s ugyanúgy
u és
v közül is. Ez viszont összesen legfeljebb három pont. Az ellentmondás bizonyítja a feladat állítását.