Max length of a path in a connected graph

Question

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?

Answer 1

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.

Answer 2

You have come up with a good idea but there are a few things you need to fix.

Firstly, the idea behind assuming $i,j\ge k/2$ is valid (reverse the path if necessary) but you should give some explanation.

Secondly, the path $S$ might consist of a single edge and no extra vertices. Then your path $$u_1,\ldots,u_i,v_j,\ldots,v_1$$ (note typo in your post) might have just $k$ vertices, which is not a contradiction.

However, there is another mistake here: a path of length $k$ has $k$ edges, not $k$ vertices, so your path $P$ should actually be $u_1,u_2,\ldots,u_{k+1}$, or even better $$u_0,u_1,\ldots,u_k\ .$$ Now you can choose your $u_i$ to be at least halfway along the path (counting edges not vertices) and so you can assume $i\ge k/2$. Doing the same for the other path, you now consider $$u_0,\ldots,u_i,\ldots,v_j,\ldots,v_0\ ,$$ where the middle set of dots may or may not contain any vertices $w_n$. How many vertices (at least) does path this have? And therefore how many edges?

Answer 3

Assume that $V(P) \cap V(Q)= \emptyset$ where $P$ and $Q$ are two longest paths with length $k$. Since $G$ is connected we know that there exists a path of length at least $1$ from a vertex of $P$ to a vertex of $Q$. Also, this paths endpoints are not the endpoints of $P$ or $Q$ otherwise we can extend our longest paths which contradicts our choice of $P$ and $Q$ as longest paths. This implies that the path from $P$ to $Q$ has endpoints that are internal vertices of $P$ and $Q$. This path from $P$ to $Q$ partitions both $P$ and $Q$ into line segments where one line segment has length at least $k\over 2$. Select both line segments whose length is at least $k\over 2$ along with the path from $P$ to $Q$ whose length is at least $1$ and we have a path whose length exceeds $k$ which is a contradiction. Thus two longest paths in a connected graph share at least one common vertex.