Intersection of all longest paths is a single common vertex – where did I go wrong

fake-proofsgraph theorysolution-verificationtrees

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.

Best Answer

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