Hogyan igazoljam, hogy egy összefüggő véges gráfban bármely két leghosszabb útnak van közös pontja?

Legyen a grafnak n pontja! Legyen W1 egy k hosszusagu leghosszabb ut. Legyen W2 egy szinten k hosszusagu leghosszab ut. Tetelezzuk fel, hogy W1 es W2-nek nincs kozos pontja, tehat diszjunktak. Ekkor a graf tobbi pontjat csak W1, vagy W2 melle helyezhetjuk el, es egy pont nem lehet egyszerre osszekotve W1-el es W2-vel, mert akkor egy hosszabb utat kapnank. Igy viszont a graf nem osszefuggo, mert W1 es W2 kozott nincs el (ekkor nem lennenek a leghosszabbak), kozos pontjuk sincs (ebbol indultunk ki), es pontokat a grafhoz teve sem valtozik a helyzet, ld. fentebb. Tehat roviden, ha letezik ket diszjunkt leghosszabb ut a grafban, a graf nem osszefuggo. (Forditva nem igaz.)