I'm working in the following graph theory excercise:

Prove that if $P$ and $Q$ are two longest paths in a connected graph, then $P$ and $Q$ have at least one vertex in common.

Through a graphic way it have been easy to show that condition in every graph, but is there a formalization that could help me to show it? Thanks in advance for any help or hint.


Say we have two paths $P$ and $Q$ with no vertices in common. Since the graph is connected, there most be a path from any vertex in $P$ to any vertex in $Q$. Take one such path. Take a part $R$ of that path with the property that one end point is in $P$, the other end point is in $ Q$, and otherwise it shares no vertices with $P$ or $Q$. By our assumption that $P$ and $Q$ have no vertices in common, $R$ has length at least $1$.

Now there are four paths that go from one end point of $P$, follows $P$ until it reaches $R$, then follows $R$ all the way to $Q$ and then follows $Q$ to an end point of $Q$. At least one of these four must necessarily be longer than both $P$ and $Q$, meaning $P$ and $Q$ cannot be longest paths.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.