Problem
COM-B2-M04-P020 Two Longest Paths
Prove that in every finite connected graph, any two paths of maximum length have at least one common vertex.
Suppose two longest paths are disjoint and connect them by a shortest path.
Let two maximum-length paths \(P\) and \(Q\) be disjoint. Denote their length by \(L\). Since the graph is connected, there is a path joining some vertex \(x\) of \(P\) to some vertex \(y\) of \(Q\). Choose such a joining path as short as possible; then its internal vertices do not lie on \(P\) or \(Q\).
The vertex \(x\) splits \(P\) into two parts whose lengths sum to \(L\). One of these parts has length at least \(\frac{L}{2}\). Similarly, \(y\) splits \(Q\) into two parts, one of length at least \(\frac{L}{2}\).
Take the longer part of \(P\), then the joining path from \(x\) to \(y\), then the longer part of \(Q\). This is a simple path: the internal vertices of the joining path are outside \(P\) and \(Q\), and \(P\) and \(Q\) are disjoint.
Its length is at least \(\frac{L}{2}+1+\frac{L}{2}=L+1\), because the joining path has positive length. This is greater than the maximum length \(L\), a contradiction. Therefore two longest paths must share a vertex.
A strong extremal-principle problem: one must choose a shortest bridge between two extremal objects.