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 élt (ami a és a csúcsot köti össze). Egészítsük ki ezt egy tovább már nem bővíthető úttá. (Ez biztosan megtehető, hiszen a feladat egyik feltétele szerint minden út hossza legfeljebb lehet.) Ha és a csúcsokat él köti össze, akkor ezzel az éllel a út kört határoz meg, ami tartalmazza a kiválasztott élt. ( nem állhat az egyetlen é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 és is legalább csúccsal van összekötve; ezek a csúcsok valamennyien -hoz tartoznak, ellenkező esetben ugyanis legalább az egyik végén bővíthető lenne egy további éllel és annak (-n kívül eső) végpontjával. Mivel feltettük, hogy és nincs egymással összekötve, a és a csúcsok valamennyi szomszédja a pontok közül kerül ki; ezek száma . Ebből következik, hogy a pontok között van olyan , amely -nel és -mel is össze van kötve. Így az minden éle benne van a vagy az körök valamelyikében, tehát a él is.
II. megoldás. , 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 összefüggő. Indirekt bizonyítunk: tegyük föl, hogy az és csúcsokat öszekötő él nincs benne körben. Ha a gráfból ezt az élt elhagyjuk, a kapott gráf már nem összefüggő, hiszen benne az -et -vel összekötő utat az éllel (immáron -ben) kiegészítve kört kapnánk. Mivel az él visszahúzásával az összefüggő gráffá válik, két összefüggő komponensre bomlik: az csúcsot tartalmazó komponensét jelölje (). Legyen felső egész-része ; megmutatjuk, hogy az gráfban létezik az -ből induló, hosszúságú út. Ehhez csupán azt kell észrevennünk, hogy -ben minden, -től különböző pont foka legalább (ugyanitt foka legalább ). Ha pedig egy (-beli) út hossza , akkor foka legalább lévén, az pontokon kívül még legalább egy további csúccsal is össze van kötve, tehát az előbbi út 1-gyel meghosszabbítható, stb. Végül, ha egy hosszúságú út (-ben) -ből -be, hasonlóan egy hosszúságú út (-ben) -ből -ba, akkor az ezek összekapcsolásával keletkező út hossza , ami ellentmondás. |