Let $k$ be the maximum length of a path in a connected graph $G$. If $P, Q$ are paths of
length $k$ in $G$, prove that $P$ and $Q$ have a common vertex.
My solution:
Suppose that $P$ and $Q$ are vertex disjoint. Let $P = (u_1, u_2,…,u_k)$ and $Q = (v_1, v_2,…,v_k)$. Let $S = (u_i = w_1, w_2,…,w_l = v_j)$ be the shortest path form a vertex in $P$ to a vertex in $Q$. This path exists because $G$ is connected. $w_2, w_3,…,w_{l-1}$ are not vertices in $P$ and $Q$ since $S$ is the shortest path. Assume that $i, j >= k/2$. The path $u_1, u_2,…, u_i, w_2,…, w_{l-1}, u_j, u_{j-1},…, u_1$ has length at least $i + j + 1 >= k + 1$. And therefore a contradiction.
Is this correct?
Best Answer
Your proof is very close, but it is not valid to assume that $i,j\geq k/2$ because they may not be. Instead, we will change where the path starts and ends depending on whether or not this is true. If $i<k/2$, start the path at $u_k$, but if $i\geq k/2$ start the path at $u_1$. Similarly, if $j\leq k/2$ end the path at $v_k$, but if $j>k/2$ end the path at $v_1$. Then the path is (segment in $P$), $S$, (segment in $Q$). Now we have arrived at your contradiction of constructing a longer path.