Prove that every two longest paths have at least one vertex in common

Question Detail: 

If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common.

I think that that common vertex should be in the middle of both the paths. Because if this is not the case then we can have a path of length $>k$. Am I right?

Asked By : Saurabh

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2615

Answered By : Luke Mathieson

EDIT Updated slightly to make explicit that $P'$ may only be of length one.

Assume for contradiction that $P_{1} = \langle v_{0},\ldots,v_{k}\rangle$ and $P_{2} = \langle u_{0},\ldots,u_{k}\rangle$ are two paths in $G$ of length $k$ with no shared vertices.

As $G$ is connected, there is a path $P'$ connecting $v_{i}$ to $u_{j}$ for some $i,j \in [1,k]$ such that $P'$ shares no vertices with $P_{1} \cup P_{2}$ other than $v_{i}$ and $u_{j}$. Say $P' = \langle v_{i},x_{0},\ldots,x_{b},u_{j}\rangle$ (note that there may be no $x_{i}$ vertices, i.e., $b$ may be $0$ - the notation is a bit deficient though).

Without loss of generality we may assume that $i,j \geq \lceil\frac{k}{2}\rceil$ (we can always reverse the numbering). Then we can construct a new path $P^{*} = \langle v_{0},\ldots,v_{i},x_{1},\ldots,x_{b},u_{j},\ldots,u_{1}\rangle$ (by going along $P_{1}$ to $v_{i}$, then across the bridge formed by $P'$ to $u_{j}$, then along $P_{2}$ to $u_{0}$).

Obviously $P^{*}$ has length at least $k+1$, but this contradicts the assumption that $G$ has no paths of length greater than $k$.

So then any two paths of length $k$ must intersect at at least one vertex and your observation that it must be in the middle (if there's only one) follows as you reasoned.