Bizonyítsa be, hogy nincs olyan 9 személyből álló társaság, ahol az embereknek rendre 7,7,7,6,6,6,4,4 ismerősük volna! (Az ismerettségek kölcsönösek)?

Vegyük azt a gráfot, ahol a csúcsok jelölik a társaság tagjait, két csúcs között akkor fusson él, hogyha akikhez azok rendelve lettek, ismerik egymást, a felsorolt számok pedig a csúcsokhoz rendelt fokszámok.

Tudjuk, hogy az élek száma úgy is kiszámolható, hogy fokszámösszeg/2, esetünkben ez 47/2, tehát a gráfnak 23,5 éle van, ez meg ugye nem lehet. Tehát nincs ilyen gráf, tehát nincs ilyen társaság sem.