1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Hint: what happens if you "join" one of the endpoints of P to one of Q with an edge? $\endgroup$ – user39280 Jan 15 '14 at 22:39
  • $\begingroup$ @dado There need not be an edge joining an endpoint of $P$ to an endpoint of $Q$. $\endgroup$ – bof Jan 15 '14 at 23:14
  • $\begingroup$ @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. $\endgroup$ – user39280 Jan 16 '14 at 10:18
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.