Gallai's conjecture on longest paths Gallai conjectured that the longest paths of a graph have a common vertex but counter examples are known to prove it wrong. Are there known bounds on how close the possible pairwise common vertices of the longest paths must be, say, as function of the number of the graph's edges?
 A: Let's begin by looking at a counterexample to Gallai's conjecture with $12$ vertices and $15$ edges.

In this graph, any longest path starts at one of the leaf vertices and ends at another, so it misses a third leaf vertex, as well as one of the degree-$3$ vertices. (It's also possible to miss two of the leaf vertices, and get everything else.) If we look at two longest paths, they will have at least $8$ common vertices: at least one of the outside leaf vertices, and at least $7$ of the degree vertices.
Suppose we're looking at four longest paths $P_1, P_2, P_3, P_4$, and we have two vertices $v,w$ such that $v$ is a common vertex of both $P_1$ and $P_2$, while $w$ is a common vertex of both $P_3$ and $P_4$. There's a few ways we could ask the question about the distance between $v$ and $w$:

*

*If we can choose $P_1, P_2, P_3, P_4, v, w$ to maximize the distance, we could end up with $d(v,w) = 5$: they could be both leaf vertices.

*For a fixed choice of paths, we might end up with no leaf vertices common to $P_1$ and $P_2$, or $P_3$ and $P_4$. However, we should still be able to pick $v,w$ with $d(v,w) \ge 3$.

*However, for any choice of $P_1, P_2, P_3, P_4$, there is at least one vertex common to all $4$ (just by counting, there must be at least $4$ such vertices). So we can't put a lower bound on $d(v,w)$ at all, if $v$ and $w$ are chosen to minimize the distance.

We could generalize this graph by subdividing each edge $k$ times; then we get a graph with $15k+12$ vertices and $15k+15$ edges. To preserve the structure of the longest paths, we should probably subdivide the edges incident to the leaf vertices a few more times than that. For the first and second version of the question above, the answer is that $d(v,w)$ could be as high as linear in the number of vertices (or edges).
However, it's not clear to me that a weaker version of Gallai's conjecture is false, and for all I know it's possible that any four longest paths in any connected graph have a common vertex. If that's the case, the answer to the third version of the question might be $0$ for all graphs.
