52.          Nyilván nem változik a feladat, ha f(x,y) értéke az x és y közti összes séta közül a legkisebb súlyú séta súlya. Hagyjunk el a gráfból éleket mindaddig, amíg összefüggő marad és minden x,y csúcspárra f(x,y) értéke változatlan marad. Azt állítjuk, hogy az így kapott gráf fa. Ha ezt belátjuk, akkor kész vagyunk, hiszen f(x,y) csak e fa éleinek értékét veheti fel. – Tegyük fel, hogy van a gráf­ban egy C kör, és legyen C legnagyobb értékű éle e=ab. Ha ezt az élet elhagyjuk, akkor minden olyan x,y-ra változatlan marad f(x,y), amelyet összekötő legkisebb súlyú séta nem tartalmazza e-t. Ha vi­szont tartalmazza, akkor e helyettesíthető a C kör a és b közötti másik útjával. Ennek súlya nem na­gyobb e értékénél, így a kapott séta súlya sem lesz nagyobb az eredeti sétáénál. Vagyis f(x,y) most sem nőtt (nyilván nem is csökkenhetett). e tehát elhagyható, amivel állításunkat igazoltuk: mindaddig hagyhatunk el a kívánt módon élt, amíg fához nem jutunk.