# Connected Graph

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

If I assume to the contrary that there are no vertices in common how can I arrive at a contradiction?

• Hint: what happens if you "join" one of the endpoints of P to one of Q with an edge? – user39280 Jan 15 '14 at 22:39
• @dado There need not be an edge joining an endpoint of $P$ to an endpoint of $Q$. – bof Jan 15 '14 at 23:14
• @bof I know! In fact, what i meant was: if you join the endpoints (with a possibly imaginary edge!), see what happens. It was a way to tell the user: the contradiction you are looking for is finding a longer path. – user39280 Jan 16 '14 at 10:18

Suppose that $P$ and $Q$ are both longest paths (and thus have equal length $l$). Assume that they have no vertices in common. There are now two vertex-disjoint paths. Because the graph is connected, we know there is a path from a vertex $p\in P$ to a vertex $q\in Q$ with length at least $1$ that is disjoint with $P$ and $Q$, apart from $p$ and $q$. Now, $p$ and $q$ divide $P$ and $Q$ in two halves (if they are not one of the endpoints). Take the longer half of both $P$ and $Q$ and connect them to the endpoints $p$ and $q$ of the path between $p$ and $q$. Because the longer halves of both $P$ and $Q$ have as least length $\frac l2$ and the path between them has as least length $1$, the new path has length $$l'\geq \frac l2+1+\frac l2>l$$ We have thus found a path with length strictly greater than $l$, and thus our assumption that $P$ and $Q$ are vertex-disjoint must have been wrong. We conclude that every pair of longest path shares at least one vertex.
Let $n$ be the longest path length, let $P=p_0p_1\ldots p_n$, $Q=q_0,q_1\ldots q_n$. Let $R=r_0r_1\ldots r_m$ be a path that is minimal among those with start point in $P$ and end point in $Q$ (such paths exist by connectivity). So $r_0=p_i$, $r_l=q_j$ for some $i,j$. If $r_k$ is in $P$ then $r_k\ldots r_m$ must be at least as long as $R$, i.e. $k=0$. Likewise if $r_k$ is in $Q$ then $r_0\ldots r_k$ is at least as long as $R$, hence $k=m$. We obtain the paths $$p_0p_1\ldots p_i=r_0\ldots r_m=q_jq_{j+1}\ldots q_n$$ $$p_0p_1\ldots p_i=r_0\ldots r_m=q_jq_{j-1}\ldots q_0$$ $$p_np_{n-1}\ldots p_i=r_0\ldots r_m=q_jq_{j+1}\ldots q_n$$ $$p_np_{n-1}\ldots p_i=r_0\ldots r_m=q_jq_{j-1}\ldots q_0$$ of lengths $i+m+n-j$, $i+m+j$, $n-i+m+j$, $n-i+m+n-j$. Since each of these must be $\le n$, their sum must be $\le 4n$. So $$4n\ge (i+m+n-j)+(i+m+j)+(n-i+m+j)+(n-i+m+n-j)\\=4n+4m.$$ Hence $m=0$ and $p_i=q_j$ is a common vertex of $P$ and $Q$.