Feladat: B.4079 Korcsoport: 18- Nehézségi fok: könnyű
Megoldó(k):  Éles András ,  Kalina Kende ,  Keresztfalvi Tibor ,  Kiss Melinda Flóra ,  Kiss Réka ,  Lovas Lia Izabella ,  Nagy Donát ,  Perjési Gábor ,  Réti Dávid ,  Strenner Péter ,  Tossenberger Anna ,  Tóth László Márton ,  Tubak Dániel ,  Varga László ,  Zieger Milán 
Füzet: 2008/november, 478 - 479. oldal  PDF file
Témakör(ök): Gráfok összefüggősége, Indirekt bizonyítási mód, Feladat
Hivatkozás(ok):Feladatok: 2008/március: B.4079

Legyen G olyan egyszerű gráf, amelyben a leghosszabb út k3 élből áll, és minden csúcs foka legalább k/2. Mutassuk meg, hogy G-nek minden éle benne van egy körben. (Útnak nevezzük egymáshoz csatlakozó élek egy olyan sorozatát, amely minden csúcsot legfeljebb egyszer érint.)

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. Tekintsünk a gráfban egy tetszőleges p0q0 élt (ami a p0 és a q0 csúcsot köti össze). Egészítsük ki ezt egy tovább már nem bővíthető U=pnpn-1...p1p0q0q1...qm-1qm úttá. (Ez biztosan megtehető, hiszen a feladat egyik feltétele szerint minden út hossza legfeljebb k lehet.) Ha pn és a qm csúcsokat él köti össze, akkor ezzel az éllel a pnqm út kört határoz meg, ami tartalmazza a kiválasztott élt. (U nem állhat az egyetlen p0q0 élből, mivel akkor mindkét csúcs foka 1 lenne); a továbbiakban feltehetjük, hogy nem ez a helyzet. A fokszámokra adott feltétel miatt pn és qm is legalább k/2 csúccsal van összekötve; ezek a csúcsok valamennyien U-hoz tartoznak, ellenkező esetben ugyanis U legalább az egyik végén bővíthető lenne egy további éllel és annak (U-n kívül eső) végpontjával. Mivel feltettük, hogy pn és qm nincs egymással összekötve, a pn és a qm csúcsok valamennyi szomszédja a pn-1,...,p1,p0,q0,...,qm-1 pontok közül kerül ki; ezek száma n+m<n+m+1k=k/2+k/2. Ebből következik, hogy a pn-1,...,p1,p0,q0,...,qm-1 pontok között van olyan y, amely pn-nel és qm-mel is össze van kötve. Így az U minden éle benne van a pnpn-1...ypn vagy az y...qm-1qmy körök valamelyikében, tehát a p0q0 él is.

 
II. megoldás. G, mint minden gráf összefüggő komponensekre bomlik, és ezen komponensek mindegyikére teljesül a feladat valamennyi feltétele. Az állítást ezért elegendő összefüggő gráfokra igazolnunk; ennek jegyében feltehetjük, hogy G összefüggő. Indirekt bizonyítunk: tegyük föl, hogy az a1 és a2 csúcsokat öszekötő él nincs benne körben. Ha a gráfból ezt az élt elhagyjuk, a kapott G' gráf már nem összefüggő, hiszen benne az a1-et a2-vel összekötő utat az a1a2 éllel (immáron G-ben) kiegészítve kört kapnánk. Mivel G' az a1a2 él visszahúzásával az összefüggő G gráffá válik, G' két összefüggő komponensre bomlik: az ai csúcsot tartalmazó komponensét jelölje Ai (i=1,2). Legyen k/2 felső egész-része n; megmutatjuk, hogy az Ai gráfban létezik az ai-ből induló, n hosszúságú út. Ehhez csupán azt kell észrevennünk, hogy Ai-ben minden, ai-től különböző pont foka legalább n (ugyanitt ai foka legalább n-1). Ha pedig egy (Ai-beli) aix1x2...xv út hossza v<n, akkor xv foka legalább n lévén, az ai,x1,x2,...,xv-1 pontokon kívül még legalább egy további xv+1 csúccsal is össze van kötve, tehát az előbbi út 1-gyel meghosszabbítható, stb. Végül, ha U1 egy n hosszúságú út (A1-ben) x-ből a1-be, hasonlóan U2 egy n hosszúságú út (A2-ben) a2-ből y-ba, akkor az ezek összekapcsolásával keletkező U1a1a2U2 út hossza 2n+12k2+1=k+1>k, ami ellentmondás.