Feladat: 2003. évi Kürschák matematikaverseny 2. feladata Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 2004/február, 69 - 70. oldal  PDF  |  MathML 
Témakör(ök): Gráfok összefüggősége, Részgráfok, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 2004/február: 2003. évi Kürschák matematikaverseny 2. feladata

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.

Megoldás. Rögzítsük G egy 3-színezését, melyben az egyes színekre színezett csúcsok száma (azaz a színosztályok mérete) n1, n2, illetve n3. Világos, hogy n1+n2+n3=n.
Tegyük fel, hogy két színosztály (mondjuk a piros és a zöld) nem feszít G-ben összefüggő gráfot, azaz a piros és zöld csúcsok között futó élek alkotta részgráfnak legalább két komponense van. Amennyiben e komponensek valamelyikén a színeket felcseréljük (vagyis ezen a komponensen belül a korábban zöld csúcsok pirosak lesznek, a pirosak pedig zöldek), úgy továbbra is igaz marad, hogy G bármely élének végpontjai különböző színűek. A cserével tehát G egy olyan 3-színezéséhez jutunk, melynek színosztályai másképpen osztják három csoportra G csúcsait, mint az eredeti színezés színosztályai. Ezért az új 3-színezésben vagy két, korábban azonos színű pont különböző színt kapott, vagy két, korábban különböző színű pont azonos színű lett, esetleg mindkét változásra sor kerülhetett. Ez ellentmond annak, hogy G egyértelműen színezhető 3 színnel, vagyis G bármely két színosztálya összefüggő gráfot feszít.
Ismert, hogy egy összefügő gráf élszáma legfeljebb 1-gyel kevesebb, mint pontjainak száma, ezért az első két színosztály legalább n1+n2-1, a második és harmadik színosztály legalább n2+n3-1, míg az első és harmadik színosztály legalább n1+n3-1 különböző élt tartalmaz. Az említett élek egymástól is különböznek, ezért G élszámára az (n1+n2-1)+(n2+n3-1)+(n3+n1-1)=2n-3 alsó becslést kapjuk.  □

 
Megjegyzések. 1. Többen próbálták a feladatot teljes indukcióval megoldani: az állítás 3-pontú gráfokra világos, tegyük fel, hogy a legfeljebb (n-1)-pontú gráfokra már bizonyítottuk a becslést. Ha az n-pontú, egyértelműen 3-színezhető G gráfnak minden csúcsa legalább 4-edfokú, akkor élszáma legalább 2n, így az állítás igaz. Ha van G-nek másodfokú csúcsa, akkor annak törlésével (mint az könnyen látható) egy egyértelműen 3-színezhető gráf keletkezik, melyre igaz az indukciós feltevés: legalább 2(n-1)-3=2n-5 éle van, ezért G élszáma nem kevesebb, mint 2n-5+2=2n-3. Az elintézetlen eset az, amikor G-ben a minimális fokszám 3. Sajnos, ha G egy harmadfokú v csúcsát elhagyjuk, a maradék G-v gráf nem lesz feltétlenül egyértelműen 3-színezhető: elképzelhető ugyanis G-v-nek olyan 3-színezése, melyben v szomszédai különböző színeket kapnak. Ha ezt követően pl. összehúzzuk v két azonos színű szomszédját, akkor a kapott gráf már egyértelműen 3-színezhető, azonban csupán 3-mal kevesebb éle van, mint G-nek. Az indukciós bizonyításhoz pedig legalább 4-gyel kevesebb élre volna szükség.
A bizottság nem ismer a fenti gondolatmenetet teljes indukciós bizonyítássá kiegészítő érvelést.
2. Többen igazolták, hogy a feladatban adott korlát elérhető. Világos, hogy a 3-pontú teljes gráf egyértelműen 3-színezhető, és (2n-3) éle van. Az is könnyen látszik, hogy ha egy egyértelműen 3-színezhető G gráfhoz hozzáveszünk egy új pontot, melyet G két különböző színű pontjával kötünk össze, akkor újabb egyértelműen 3-színezhető gráfot kapunk, melyre a becslés pontos lesz, ha már G-re is az volt.
3. A feladat megoldása értelemszerű módosításokkal kiterjeszthető egyértelműen k-színezhető gráfok élszámának becslésére is, azaz megmutatható, hogy tetszőleges egyértelműen k-színezhető gráfnak legalább (k-1)(n-k)+(k2) éle van. A 2. megjegyzés is kiterjeszthető: a k-pontú teljes gráf egyértelműen k-színezhető, és egy egyértelműen k-színezhető gráfhoz új pontot hozzávéve és k-1 különböző színű ponttal összekötve ismét egyértelműen k-színezhető gráfot kapunk.
4. Akkor is alkalmazható a módszerünk, ha nem az egyértelműen k-színezhető gráfok élszámát akarjuk megbecsülni, hanem csupán felső korlátunk van G k-színezéseinek számára. A megoldás gondolatmenetével felső becslést kaphatunk két színosztály által feszített komponensek számára, innen pedig a két komponens által feszített élek száma alulról becsülhető.