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.