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.

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email