Společný vrchol na nejdelší cestě
Úloha číslo: 3578
Dokažte, že libovolné dvě nejdelší cesty v souvislém grafu mají společný vrchol.
Mají také nutně společnou hranu?
Mají také nejdelší indukované cesty společný vrchol?
Řešení
Sporem – uvažme dvě nejdelší cesty \(P\) a \(Q\) bez společného vrcholu. Protože je \(G\) souvislý, vede cesta mezi nějakou dvojici vrcholů \(u\in P\) a \(v\in Q\).
Vybereme nejkratší takovou spojnici – tato už nebude obsahovat jiné vrcholy \(P\) ani \(Q\).
Označme \(u'\) vzdálenější konec cesty \(P\) od vrcholu \(u\) (je-li \(u\) uprostřed, zvolíme libovolný konec) a podobně \(v'\) pro \(v\) a \(Q\).
Potom lze nalézt delší cestu jdoucí po \(P\) od \(u'\) k \(u\), poté po spojnici k \(v\) a pak podél \(Q\) k \(v'\).
Pro hranu neplatí, vizte třeba graf \(K_{1{,}4}\)
Indukované nejdelší cesty nutně vedou mezi nejvzdálenějšími vrcholy a jejich délka je rovna vzdálenosti těchto vrcholů. Tedy např. v grafu \(K_4\) není delší indukovaná cesta než délky jedna, ovšem lze nalézt dvě hrany bez společného vrcholu.
