Feladat: B.4065 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Ágoston Tamás ,  Bodor Bertalan ,  Bóra Eszter ,  Bunth Gergely ,  Fonyó Dávid ,  Fukker Gábor ,  Gévay Gábor ,  Horváth Vanda ,  Nguyen Milán ,  Palincza Richárd ,  Peregi Tamás ,  Réti Dávid ,  Salát Zsófia ,  Strenner Péter ,  Szalkai Balázs ,  Szőke Nóra ,  Varga Bálint 
Füzet: 2009/március, 153 - 155. oldal  PDF  |  MathML 
Témakör(ök): Gráfok összefüggősége, Részgráfok, Konstruktív megoldási módszer, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 2008/február: B.4065

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.

I. megoldás. Alkalmazzunk teljes indukciót az élszám és a csúcsszám összegére, n-re. Két csúcsú ilyen gráf nincs; három csúcsú egy van, a háromszög, és arra nyilván igaz az állítás. Ekkor n=6, és ez az egyetlen ilyen gráf. Az ábrán látható az összes gráf n=6,8,9 és 10 esetén (n=7-re nincs megfelelő gráf). Ezen gráfok mindegyik csúcsa megfelelő csúcs.

 
 

Legyen n>10 és tegyük fel, hogy az állítás k<n esetén igaz. Két esetet különböztetünk meg.
1) A G gráfban van pontosan 2-fokú csúcs. Hagyjuk el ezt a csúcsot a gráfból a belőle induló két éllel együtt. Ha két szomszédját még nem köti össze él, akkor húzzuk be azt. Ekkor a megmaradt gráfban n értéke 2-vel vagy 3-mal csökken, és így az indukció szerint igaz rá az állítás. Ha egy kör valamely éle az esetleg újonnan megjelenő él, akkor vegyük az elhagyott csúcsot a hozzá tartozó 2 éllel, így újra kört kapunk; a többi kör esetén pedig nincs szükség változtatásra.
2) Minden csúcs foka legalább 3. Ekkor bármely él elhagyásával egyrészt n értéke csökken 1-gyel, másrészt a megmaradt gráfban is minden fokszám legalább 2, tehát van benne megfelelő csúcs. Nem mindegy, hogy melyik élt hagyjuk el: csak olyat hagyhatunk el, amelyik egy körön fekszik. (Mivel a gráfban minden csúcs foka legalább 2, így biztosan van benne kör.) Tekintsük a megmaradt gráfban az indukció szerint létező csúcsot. Ha ez a csúcs az elhagyott él egyik végpontjával sem esik egybe, akkor annak visszavétele után is jó lesz a keresett tulajdonságú csúcsnak. Ha pedig ezen él valamelyik végpontja, akkor az él visszavétele után erre az élre is teljesülni fog, hogy benne van egy körben ‐ éppen ezért nem választottuk tetszőlegesen az elhagyott élt.
Az állítás tehát mindkét esetben igaz n=k-ra.
 
II. megoldás. Legyen a gráfban található leghosszabb út L, ennek egyik végpontja pedig A. Egy él már biztosan kiindul A-ból, ennek másik végpontját jelölje B. Mivel a gráfban minden csúcs fokszáma legalább 2, azért A-ból legalább még egy további él kiindul. Egy ilyen él nem lehet hurokél, mert G egyszerű gráf. Az él A-tól különböző végpontja L-ben kell hogy legyen, ellenkező esetben ugyanis lenne L-nél hosszabb út a gráfban. Legyen ez a végpont C. Az L-nek az A és C csúcsot összekötő része (ami szintén út, és tartalmazza B-t) és az A ‐ C él kört alkotnak. Ez bármely A-ból induló, AB-től különböző élre elmondható. Az AB él pedig az összes ilyen körben benne van. Így minden A-ból induló él benne lesz egy körben. Tehát az A csúcs megfelelő.
 
III. megoldás. Végtelen gráfra az állítás nem igaz, hiszen például egy egyenes mentén elhelyezett, végtelen csúcsú gráfban, melyben a szomszédos csúcsokat köti össze él, nincs kör.
Tegyük föl, hogy a gráf véges, és nem igaz rá az állítás, azaz minden csúcsához van belőle kiinduló olyan él, amely nincs benne egy körben sem. Az ilyen élt a továbbiakban nevezzük rossz élnek.
Mivel a gráf minden csúcsának legalább 2 a fokszáma, biztosan tartalmaz kört.
Tekintsünk G-ben egy K1 kört. Ennek minden csúcsából kiindul egy rossz él, ami így nincs benne K1-ben. Vegyük a kör valamely C1 csúcsát, s az ebből kiinduló rossz él másik végpontját véve második csúcsnak, induljunk el C1-ből a rossz él irányában. Ennek az élnek a másik végpontja legyen C2. Legyen egy lépés az, hogy egy Ci csúcsból (i≥2) a Ci+1 csúcsba lépünk úgy, hogy Ci+1≠Ci-1, valamint a Ci és a Ci+1 csúcsot él köti össze. (A továbblépés mindig lehetséges, mert Ci fokszáma legalább 2.) Addig menjünk, amíg vissza nem érünk egy olyan csúcsba, ahol már jártunk (ez biztosan bekövetkezik, mert G véges). Ekkor sohasem juthatunk el a K1 kör valamelyik csúcsába, mert ekkor onnan C1-be is eljuthatnánk, s ezáltal a kiinduló rossz él benne lenne egy körben, ami ellentmondás. Így a visszacsatlakozásig bejártunk egy K1-től diszjunkt K2 kört. Ezután általában a Ki körnek (i≥2) vegyük egy attól a csúcstól különböző csúcsát, melynél beérkeztünk a Ki körbe, majd egy ebből kiinduló rossz élt, s ezen induljunk el a fenti módszer szerint. Kapunk egy Ki-től diszjunkt Ki+1 kört. Ez minden Kj (j<i) körtől is diszjunkt, mert ezek egy csúcsába se juthattunk el a Ki körből, hiszen ekkor ezekből a Ki körbe is visszajuthatnánk, ezzel egy rossz élt egy körbe foglalva, ami nem lehetséges. Így pedig végtelen sok diszjunkt körnek kellene lennie G-ben, ami nem lehetséges, hiszen G véges.
Ezzel ellentmondásra jutottunk, tehát a feladat állítását bebizonyítottuk.