## Common vertex on longest path

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.