58.          Tekintsük a fa végpontjait (=elsőfokú pontjait): ezek mindegyikéhez kell egy új élet illesztenünk, különben nem mehet át rajtuk kör. Ha a fának k végpontja van, akkor ezek szerint legalább [(k+1)/2] új élt be kell húznunk ahhoz, hogy a fa minden pontján menjen át él.

Most a pontok számára vonatkozó teljes indukcióval megmutatjuk, hogy ennyi éllel mindig meg is oldható a feladat. Még valamivel többet is állítunk (így ugyanis könnyebben megy az indukció): megmutatjuk, hogy [(k+1)/2] él behúzásával már elérhető az is, hogy minden él is benne legyen körben. (Ez valóban több, hiszen például az alábbi gráfban minden pont benne van körben, de a vastagabban jelölt él hídél, nem megy át rajta kör: )

                                

Még egy kicsit erősítjük állításunkat: az újonnan behúzandó élek mindegyike végpontokat köt össze. (Ha k páros, akkor a mondottak szerint nem is lehet másképp. Páratlan k esetén elképzelhető volna, hogy egy él egyik végpontja nem elsőfokú a fában, feltételünk ezt zárja ki.) Tehát a következő állítást fogjuk belátni:

Ha egy n pontú fának k elsőfokú pontja van, akkor az elsőfokú pontjai között behúzható [(k+1)/2] él úgy, hogy a kapott gráfban minden élen menjen át kör.

Állításunk könnyen igazolható, ha k=2, azaz a fának csak két végpontja van: ekkor a fa egy út, s ennek két végpontját összekötve egy olyan gráfot kapunk, amely egyetlen körből áll. A csillagra is könnyen igazolható az állítás: ha páros sok végpontja van, akkor párosítjuk a végpontokat és e párokat összekötjük, a kapott gráf egy pontban illeszkedő háromszögekből áll, minden él egy háromszögben van. Ha páratlan sok végpont van, akkor egy pont kimarad a párosításból, ezt egy tetszőleges végponttal összekötjük, így most is minden él benne van egy háromszögben.

                      

Most megmutatjuk, hogy a kezdőlépésekre igaz az állítás: n=3 esetén csak egy fa van és ez út is, csillag is; n=4 esetén pedig csak két fa van: az út és a csillag.

Tegyük fel, hogy n>4 és n–2 és n–1 pontú fákra már beláttuk állításunkat és legyen G egy n pontú fa. Ha G-ben van másodfokú pont, akkor legyen x egy ilyen másodfokú pont, legyen két szomszédja y és y’. Hagyjuk el a fából x-et, és a belőle induló két élet, és kössük össze y-t y’-vel. Ez az él nem szerepelt G-ben, hiszen G-ben nincs kör. Másrészt a kapott G’ gráf továbbra is összefüggő és körmentes, tehát fa. Másrészt eggyel kevesebb pontja van, tehát alkalmazható indukciós feltevésünk. Végül még azt kell észrevennünk, hogy G’-nek ugyanazok a végpontjai, mint G-nek, tehát az indukciós feltevés szerint behúzható közöttük [(k+1)/2] él úgy, hogy a kapott gráf minden éle benne legyen körben. De akkor az yy’ él helyére visszaillesztve az yxy’ utat ez a tulajdonsága továbbra is megmarad: az a kör, amelyik yy’ élen ment keresztül, most keresztül fog menni yx és xy’ éleken, a többi élen pedig továbbra is fog keresztül menni kör.

A továbbiakban tehát feltehetjük, hogy a végpontokon (elsőfokú pontokon) kívül a fa minden pontjának foka legalább három. Azt is feltehetjük, hogy G nem csillag, mert ezt az esetet már elintéztük. Vegyük most a gráf egy leghosszabb útját, legyenek ennek végpontjai u és v, u szomszédja az úton u’, v szomszédja v’. Ha u nem volna elsőfokú pont a fában, akkor u’-től különböző u’’ szomszédja nem szerepelhetne az út pontjai között, hiszen ez esetben volna kör a fában. De akkor az uu’’ élt hozzáilleszthetnénk az úthoz, így nagyobb utat kapnánk, ami ellentmond feltevésünknek. Tehát u – s ugyanígy v is – elsőfokú. G nem csillag, ezért u’ és v’ különböző belső pontjai az útnak. De akkor u’ és v’ fokszáma legalább kettő, de feltevésünk szerint pontosan kettő nem lehet, ezért legalább három. Ha tehát u-t és v-t elhagyjuk a gráfból, nem keletkezik új elsőfokú pont, viszont két elsőfokúval kevesebb pont lesz. A fa pontszáma kettővel csökkent, tehát indukciós feltevésünk alkalmazható: a maradó k–2 elsőfokú pont között behúzható [(k–1)/2] él úgy, hogy a kapott gráfban minden élen menjen át kör. Ha most „visszatesszük” a gráfba az uu’ és vv’ éleket és u-t összekötjük v-vel, akkor egy olyan kört kapunk, amely keresztül megy uu’, uv, vv’ éleken is. Tehát minden élen megy keresztül kör. A behúzott élek száma eggyel nőtt, azaz éppen [(k+1)/2].