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?
 A: 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.
A: 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$.
