Common vertex on longest path
Task number: 3602
Show that any two longest paths in a connected graph have a common vertex.
Must they also have a common edge?
Must the two longest induced paths have a common vertex?
Solution
By contradiction – consider two longest paths \(P\) and \(Q\) without a common vertex. Because \(G\) is connected, there is a path between some pair of vertices \(u\in P\) and \(v\in Q\).
We choose the shortest such connecting path – it may not contain other vertices of \(P\) or \(Q\).
Let \(u'\) be the more distant end of the path \(P\) from the vertex \(u\) (if \(u\) is in the middle, we choose either end) and similarly \(v'\) for \(v\) and \(Q\).
Then we can find a longer path leading along \(P\) from \(u'\) to \(u\), then along the connecting path to \(v\) and finally along \(Q\) to \(v'\). \bigskip
The assertion for a common edge does not hold; consider for example the graph \(K_{1{,}4}\) \bigskip
Longest induced paths must lead between two maximally distant vertices and the length of such a path equals the distance between these vertices. So e.g. in the graph \(K_4\) there is no induced path of length longer than one, and of course we can find two edges without a common vertex.
