1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

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