Do any three longest paths in a connected graph have a vertex in common?
OPG_three_longest_paths_common_vertex
Source: Open Problem Garden: do_any_three_longest_paths_in_a_connected_graph_have_a_vertex_in_common
Status partial high confidence
Gallai's 1966 conjecture that any three longest paths in a connected graph share a common vertex remains open in general. Meaningful partial results confirm the conjecture for specific graph classes (series-parallel, outerplanar, split, $H$-free graphs with linear-forest $H$), and a 2025 paper improves the best known bound on the minimum vertex set hitting all longest paths to $O(\sqrt{n})$. An attempted general proof (arXiv:2006.16245, 2020) was withdrawn by its author as erroneous.
Cited literature (2)
-
Characterizes all graphs $H$ on at most 4 vertices for which every connected $H$-free graph has a single vertex meeting all longest paths; these are exactly the linear forests, confirming Gallai's property for those graph classes.
-
Proves every connected $n$-vertex graph has a set of at most $\sqrt{8n}$ vertices intersecting all longest paths, improving the previous $O(n^{2/3})$ state-of-the-art bound.
Reviewer notes. arXiv:2006.16245 (Sarkar, 2020) claimed a full proof but was withdrawn as erroneous by the author. The Discrete Math. 2022 paper on chordal graphs (DOI 10.1016/j.disc.2022.113035) returned HTTP 403 and could not be verified; not cited. arXiv:2310.03849 (Gutiérrez–Valqui, 2023) focuses on Smith's and Hippchen's conjectures about pairwise cycle/path intersections in $k$-connected graphs, not the 3-path Gallai conjecture.
Discussion
It is a well-known exercise that every two longest paths in a connected graph have a common vertex. Skupien [S] showed connected graphs where 7 longest paths do not share a common vertex.
Bibliography
-
★
[G]T. Gallai, Problem 6. In Theory of Graphs (Proc. Colloq., Tihany, 1966) , 362 Academic Press, New York, 1968. -
[?]Z. Skupień, Smallest sets of longest paths with empty intersection. Combin. Probab. Comput. 5 (1996), no. 4, 429–436.