Gráfelmélet. Van-e olyan társaság, ahol minden embernek különböző száma ismerőse van?

Mellesleg olyan gráfokat könnyű konstruálni ahol az N pontból N-1-nek különböző lesz a fokszáma. Indukcióval: legyen Gn egy ilyen gráf n ponttal, a fenti érvelés szerint vagy van benne 0 fokszámú pont vagy van benne n-1 fokszámú. Ha van benne 0 fokszámú pont akkor nézzük a G'n komplemens gráfot helyette, nyilvánvalóan ugyanannak az n-1 pontnak lesz különböző a fokszáma. Tehát bátran feltehetjük hogy van egy n pontszámú Gn gráfunk amiben nincs 0 fokszámú pont és n-1 pontnak különbözik a fokszáma. Most addjunk hozzá hogy egy 0 fokszámú pontot és máris van egy n+1 pontú gráfunk amiben n pontnak van különböző fokszáma.

Ez n>=3 -ra igaz. Hogy az indukció elejét bizonyítsuk, vegyünk egy AB,BC gráfot, A és B fokszáma különböző tehát máris megalkottuk a 3 pontos gráfot.

Összefoglalva az eredeti kérdésre a választ: n pontra biztosan van legalább kettő aminek azonos a fokszáma és olyan gráfot lehet is konstruálni aminek pont kettőnek lesz azonos a fokszáma.

Hogy a konstrukció jobban látszódjon:

Három pontra ugye AB,BC

Négy pontra AB,BC,D

Öt pontra először vegyük a komplemenst:AC,AD,BD,CD és ehhez ha hozzácsapsz egy E pontot akkor már meg is van.