2
$\begingroup$

I was trying to prove that all longest paths of a tree share a common vertex.

My proof: Consider any two longest paths $P_1 = (u_1, u_2, \cdots, u_k)$ and $P_2 = (v_1, v_2, \cdots, v_k)$ (the paths must have the same length because otherwise, one would be shorter than the other, and hence not the longest path anymore). If these two paths do not share any vertex, and since the graph is connected, there must be a path $Q$ from some vertex of path $P_1$ to some vertex in path $P_2$. Let $i$ be the largest index, for which $u_i\in Q \cap P_1$ and $j$ be the smallest index for which $v_j \in Q \cap P_2$. Then the subpath, $Q'$, of $Q$, starting from $u_i$ and ending with $v_j$ has no edges in common with either $P_1$ or $P_2$. Now we construct a path as follows: Let $P_1' = (u_1, u_2, \cdots, u_i)$ if $i > k/2$ or $(u_k, u_{k - 1}, \cdots, u_i)$ otherwise. Similarly, let $P_2' := (v_j, v_{j - 1}, \cdots, v_1)$ if $j > k/2$ or $(v_j, v_{j + 1}, \cdots, v_k)$ otherwise. Then the path $P = P_1' || Q' || P_2'$ has length $> |P_1'| + |P_2'| > k$, contradicting the maximality of $P_1$ and $P_2$. Thus we must have that any two longest paths share a vertex. Moreover the common vertex has to be the middle vertex of both the paths (if they are even length paths it is any one of the two middle vertices), because otherwise, we can again construct a longer path leading to a contradiction. Now if $k$ is odd we are done because then we would take any longest path, and it has exactly $1$ middle point and every other longest path has to pass through that middle point. If $k$ is even, and we take any longest path, it has two middle points. However, if any other longest path passes through one of the middle points, every other longest path also has to pass through the same middle point because otherwise, we can again construct a path of length $k + 1$. $\blacksquare$

Now it apparently seems that this proof works for any connected graph, and not just only trees. Thus what I might have proved is: all longest paths in any connected graph share a common vertex. However, I know that there are counterexamples to this statement. Thus either, the above proof is wrong, or somehow it uses the fact that the underlying graph is a tree. Can anyone point out? I am totally flabbergasted.

$\endgroup$
3
  • 1
    $\begingroup$ Honestly, the second part of your reasoning is incomprehensible even for trees. The two longest paths $P_1$ and $P_2$ can have several vertices in common, so you should clarify your reasoning in the second part for both odd and even $k$. How is the longer path constructed if the middle vertex is not a common vertex of $P_1$ and $P_2$, but there are many other common vertices? $\endgroup$
    – kabenyuk
    Commented Aug 22, 2022 at 6:18
  • $\begingroup$ What I meant is the following: Suppose the common vertex of the two paths is $u_i = v_j$. Now again we define $P_1'$ and $P_2'$ in the exact same manner as before. Then $P_1'|| P_2'$ has length $> k$. $\endgroup$
    – QED
    Commented Aug 22, 2022 at 16:32
  • 2
    $\begingroup$ It should be noted that there are graphs where there are longest paths that do not all share a common vertex [even though any $2$ such paths intersect], but this is nontrivial indeed. The following paper sciencedirect.com/science/article/pii/S0166218X19301969 contains references $\endgroup$
    – Mike
    Commented Aug 22, 2022 at 23:54

1 Answer 1

2
$\begingroup$

No, you proved that every pair of longest paths has a common vertex. You didn't prove anything about the intersection of all longest paths that may be empty. Moreover the second part is wrong for general connected graph, because two paths may have common vertices before and after their middle vertices. In this case there is no way to extend any of this path just going through the middle vertex of the other path. Consider a path graph on $7$ vertices $v_1, v_2, \ldots, v_7$ and add one more vertex $u$ adjacent to $v_3$ and $v_5$. This graph contains exactly two longest path $v_1v_2v_3v_4v_5v_6v_7$ and $v_1v_2v_3uv_5v_6v_7$. This paths share each of $6$ vertices other than the middle one.

P. S. Also there is a small inaccuracy. I guess you mean $u_i$ to be the last vertex of $Q$ belonging to $P_1$. But it could have the smallest index $i$ among all vertices of $u_i \in V(P_1) \cap V(Q)$, if $Q$ starts for example from $u_k$ and goes through $u_{k - 1}$. The same situation with $j$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .