# 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.

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.