Feladat: 3.2. Egy öttagú társaságban nincs három ember, akik ismernék egymást, és nincs három ember, akik közül egyik sem ismerné a másikat. Bizonyítsuk be, hogy leültethetők egy kerek asztal köré úgy, hogy mindegyikük ismerje a két szomszédját, de ne ismerje a másik két embert.
Megoldás: 3.2
Válasszuk ki a társaság egy tetszőleges
A tagját, és nézzük az ismerőseit. Biztos, hogy ismerősei közül senki nem ismeri a másikat, különben ők ketten és
A három ember volna, akik kölcsönösen ismernék egymást. Viszont ugyanezért
A-nak nem lehet kettőnél több ismerőse. Másrészt nézzük azokat, akiket nem ismer. Ezek közül mindenki ismeri egymást, mert ha ketten nem ismernék egymást, akkor ők és
A olyan három ember volna, akik közül senki nem ismer senkit. Viszont ezért nem lehet
A-nak kettőnél több ,,nem-ismerőse" sem. Összesen négyen vannak rajta kívül, tehát két embert ismer, azok nem ismerik egymást - és két embert nem ismer, akik viszont ismerik egymást. Ezt a társaság mindegyik tagjáról elmondhatjuk. Ha gráffal ábrázoljuk az ismeretségeket, akkor egy 2-reguláris ötpontú gráfot kaptunk. Nyilvánvaló, hogy egyetlen ilyen van: az ötpontú kör (átló nélkül). És éppen ezt állítja a feladat állítása is.