Feladat: F.2940 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Csörnyei Marianna ,  K. L. 
Füzet: 1994/január, 17 - 19. oldal  PDF  |  MathML 
Témakör(ök): Gráfok komplementere, Teljesgráfok, Feladat
Hivatkozás(ok):Feladatok: 1993/január: F.2940

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A feladat az 1992. évi Nemzetközi Matematikai Diákolimpia 3. feladatának (ld. KöMaL 1993/1. szám 3‐4. oldal) módosítása.
Most is fel fogjuk használni a következő tételt: ha egy gráfnak legalább 6 pontja van, akkor a gráf vagy a komplementere biztosan tartalmaz háromszöget, vagy másképpen fogalmazva: ha egy legalább 6 pontú teljes gráf éleit kiszínezzük két színnel, akkor a gráf biztosan tartalmaz egyszínű háromszöget.
A 10 pontú teljes gráfnak (102)=45 éle van. Megmutatjuk, hogy ha a gráfnak legalább 41 éle van (azaz a teljes gráfból legfeljebb 4 él hiányzik), akkor mindig tartalmaz egyszínű háromszöget. Ezen kívül példát mutatunk olyan gráfra, amelynek 40 éle van, és nem tartalmaz egyszínű háromszöget.
Ezekből pedig következik, hogy a gráfnak legfeljebb 40 éle lehet.
Ha a teljes gráfból legfeljebb 4 él hiányzik, akkor válasszuk ki mindegyik hiányzó élnek valamelyik végpontját, és ezt a legfeljebb 4 kiválasztott pontot hagyjuk el a gráfból. Ezzel az eredetinek egy olyan részgráfját kapjuk, amelynek legalább 6 pontja van, és amelyben már nincsenek ,,hiányzó'' élek, vagyis a részgráf teljes. Az előbb idézett tétel szerint tehát a részgráf tartalmaz egyszínű háromszöget. A háromszög viszont az eredeti gráfnak is része. Ezzel igazoltuk, hogy ha a gráfnak legalább 41 éle van, akkor tartalmaz egyszínű háromszöget.
Most mutatunk egy 10 pontú, 40 élű gráfot, amelynek éleit ki lehet színezni úgy, hogy ne tartalmazzon egyszínű háromszöget (1. ábra). Megjegyezzük, hogy az öt hiányzó él közül semelyik kettőnek nem lehet közös végpontja, mert ellenkező esetben el lehetne hagyni négy pontot (az egyiket a két él közös végpontjának választva) úgy, hogy a megmaradó 6 pontú gráf teljes legyen, az pedig biztosan tartalmaz egyszínű háromszöget.

 
1. ábra
 
2. ábra

 
Ez a feltétel máris meghatározza, hogy mi a keresett gráf; nekünk csak a színezést kell előírnunk.
A jobb áttekinthetőség érdekében folytonos szakaszokkal ábrázoljuk a piros éleket, a kék színűeket most nem rajzoljuk be. A teljes gráfból kimaradó 5 élt szaggatott vonal jelzi. A 2. ábráról jól látszik, hogy a gráfban nincs egyszínű háromszög.
 
Megjegyzések. 1. A felhasznált segédtétel a következőképpen bizonyítható be. Legyen A a gráf egy tetszőleges pontja. Mivel A-ból legalább 5 él indul ki, az élek között van három egyszínű, mondjuk piros. Legyen ezek végpontja B,C és D.
Ha a B,C,D pontok közül kettőt piros él köt össze, akkor ez a két pont A-val együtt egy piros háromszöget alkot. Ha pedig a BCD háromszög élei közül egyik sem piros, akkor BCD egy kék háromszög.
 
3. ábra
 
2. A feladatot akárhány pontú gráfra is általánosítani lehet a Turán-tétel segítségével.
A Turán-tétel arra ad választ, hogy legfeljebb hány éle lehet egy n pontú gráfnak, ha az nem tartalmaz k pontú teljes részgráfot; sőt a maximális élszámú gráfokat is leírja.
Maximális élszámú gráfot úgy kapunk, hogy az n csúcsot ,,nagyjából'' k-1 egyenlő részre osztjuk (azaz két tetszőleges részben a csúcsok számának különbsége legfeljebb 1 lehet), és azokat a pontokat kötjük össze, amelyek különböző részbe kerültek.
A feladatban ‐ a segédtétel alapján ‐ csak olyan gráfok jöhetnek szóba, amelyek nem tartalmaznak 6 pontú teljes részgráfot. Legfeljebb hány éle lehet egy ilyen gráfnak?
Ismerve a Turán-tételt, osszuk fel a pontokat 5, nagyjából egyenlő részre, és kössük össze azokat a pontpárokat, amelyek különböző részbe kerültek (az olimpiai feladatban egy 1- és négy 2-elemű, feladatunkban pedig öt 2-elemű rész szerepelt).
Az az érdekes, hogy ezt a gráfot ki lehet színezni két színnel úgy, hogy ne tartalmazzon egyszínű háromszöget (3. ábra, 4. ábra).
 
4. ábra
 
A Turán-tételből a gráf egyértelműsége is következik.
 
Kós Géza