Feladat: 3.10.
Egy üdülő bármely három lakója között van kettő, aki nem ismeri egymást, de bármely hét lakója között van kettő, aki ismeri egymást. Az üdülés befejeztével mindenki megajándékozza minden ismerősét egy-egy ajándékkal. Bizonyítsuk be, hogy
n lakó esetén legfeljebb
6n ajándéktárgyat adtak át! (OKTV 1986, I. kategória, döntő)
Hogyan fogalmazható át a feladat gráfelméleti nyelvre?
Megoldás: 3.10
A feladat ugyan nem mondja ki, de a megfogalmazása implicite tartalmazza, hogy az ismeretségek kölcsönösek. Tehát egy
n pontú gráfról van szó, amelyről egyrészt tudjuk, hogy nincs benne háromszög (három pontú teljes részgráf), másrészt azt is tudjuk, hogy bármely hét pontja között van kettő, amelyeket él köt össze (a komplementerében nincs hétpontú teljes gráf).
Az átadott ajándékok száma éppen a gráf pontjai fokszámának összege. (Vigyázat! Most minden élhez KÉT ajándék tartozik, tehát az ajándékok fokszáma = a fokszámösszeggel.)
Azt kell belátnunk, hogy egy ilyen gráfban a fokszámok összege legfeljebb
6n, vagyis hogy egy ilyen gráfban legfeljebb
3n él van. (Az Euler-összefüggés szerint a fokszámok összege az élszám kétszerese.)
Ennél valamivel többet látunk be, éspedig azt, hogy minden pont foka legfeljebb hat. Ez pedig következik abból, hogy egy pont szomszédai között nem futhat él, hiszen akkor lenne három pontú teljes gráf. Másrészt ha egy pontnak hét vagy több szomszédja volna, akkor volna hét pont, amelyek között nem fut él, s ezt a feladat feltétele kizárta.
A
GR.II.3.11. feladatban bizonyításra kerülő Erdős-Szekeres tétel szerint ennek az üdülőnek legfeljebb 20 lakója lehet.