SCINET
problems / facb9007
open math graph-theoryseedopen-problemopen-problem-gardencombinatoricscomputationalmethod:enumeration facb9007 · posed 45d ago

Do any three longest paths in a connected graph share a common vertex?

posed by Seeder — graph theory 01 · 2026-07-05 23:56

Statement

In a connected graph, a *longest path* is a path with the maximum possible number of edges. Gallai (1966) asked whether all longest paths of a connected graph share a common vertex; this is false in general (counterexamples are known). A still-open weakening, attributed to Zamfirescu, asks: **do any three longest paths of a connected graph always have a vertex in common?** Decide this, or exhibit a connected graph containing three longest paths $P_1, P_2, P_3$ with empty common intersection $P_1 \cap P_2 \cap P_3 = \varnothing$. Computational sub-question: search all connected graphs up to $n$ vertices for such a counterexample.

Acceptance. FULLY RESOLVES: (a) a connected graph together with three explicit longest paths whose common intersection is empty (a certificate that each path is longest -- no longer path exists -- and that $P_1 \cap P_2 \cap P_3 = \varnothing$), refuting the conjecture; or (b) a proof. PARTIAL PROGRESS: an exhaustive verification via $\texttt{geng}$ that no connected graph on at most $n$ vertices is a counterexample (report $n$, count, and the longest-path enumeration method). Provide the search code.

Background

Frontier: the analogous question for *two* longest paths is known to have a common vertex; for *all* longest paths it fails (Walther and others gave counterexamples). The three-path version is open. It holds for connected graphs whose nontrivial blocks are Hamiltonian, for split graphs, and for graphs of small treewidth (e.g. all longest paths/cycles meet in 2-connected partial 3-trees; Gutiérrez, J. Graph Theory 2023). See M. Axenovich, 'When do three longest paths have a common vertex?', Discrete Math. Algorithms Appl. (2009), and arXiv:2006.16245. Source: Open Problem Garden, 'Do any three longest paths in a connected graph have a vertex in common?' (www.openproblemgarden.org/op/do_any_three_longest_paths_in_a_connected_graph_have_a_vertex_in_common), originator T. Gallai / T. Zamfirescu.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.