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

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

Definitions and mathematical statement

Let $G=(V,E)$ be a finite nonempty connected simple undirected graph. A path is a sequence $v_0,\ldots,v_t$ of distinct vertices with an edge between each consecutive pair; its length is $t$, its number of edges. Define $L(G)$ to be the largest length of a path in $G$. A longest path is any path attaining $L(G)$.

The conjecture states that for every such $G$ and every three longest paths $P_1,P_2,P_3$, \[ V(P_1)\cap V(P_2)\cap V(P_3)\ne\varnothing. \] The common vertex may depend on the chosen triple. It need not be an endpoint of any path, and no common edge is required. Allowing repetition among the three paths does not strengthen the distinct-path case. For a graph with one vertex, the length-zero path uses that vertex.

The assertion is about a triple's simultaneous intersection, which does not follow merely from each pair having a nonempty intersection. It also does not assert that a single vertex belongs to every longest path of the graph: different triples can have different witnesses. Paths are not required to be induced; edges between nonconsecutive path vertices are permitted in $G$.

"Longest" refers to maximum length among all paths in the entire graph, not just to inclusion-maximal paths or to shortest paths between their ends. A negative resolution would consist of a connected graph and three globally longest paths whose three vertex sets have empty intersection.

Short English statement

In every connected graph, must any selected three longest paths share at least one vertex?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 1 October 2026. This attempt keeps the catalogue statement above, checks primary literature, and develops a restricted argument with an adversarial gap audit. The proofs below are the mathematical output of this attempt, not a claim of novelty or external certification.

Literature and attack plan.

A 2020 preprint by Sarkar [R1] claims an affirmative solution. Its title or abstract alone is not a verification of that proof. The September 2026 primary paper of Ma, Ning and Zhao [R2], in its concluding problems, still explicitly asks whether three longest paths must meet. We therefore do not adopt the claimed solution or assert a settled literature status. The work below independently proves pairwise intersection and proves the triple assertion for trees. It isolates the missing Helly property in a general graph.

Any two longest paths intersect.

Let $L=L(G)$ and suppose longest paths $P,Q$ are disjoint. Because $G$ is connected, choose a shortest path $R$ joining their vertex sets, with endpoints $p\in P,q\in Q$. No internal vertex of $R$ belongs to $P$ or $Q$, or a shorter joining path would exist. Its length $r$ is at least one.

Deleting $p$ as a dividing point splits $P$ into two arms whose lengths sum to $L$; one has length at least $\lceil L/2\rceil$. The same holds at $q$ in $Q$. Follow a longer arm of $P$ toward $p$, then $R$, then a longer arm of $Q$ away from $q$. Since the two paths are disjoint and the interior of $R$ avoids both, the resulting sequence is a simple path. Its length is at least \[ 2\lceil L/2\rceil+r>L, \] a contradiction. Thus any two longest paths meet. This proof includes $L=0$: a connected graph with a length-zero longest path has only one vertex, so disjoint longest paths cannot occur.

A three-path Helly lemma for trees.

Let $T$ be a tree, and let $Q_1,Q_2,Q_3$ be any paths in it, not necessarily longest. Suppose they meet pairwise. Choose \[ a\in Q_1\cap Q_2,\quad b\in Q_2\cap Q_3, \quad c\in Q_1\cap Q_3. \] If two of $a,b,c$ coincide, that vertex already lies in all three paths. Otherwise consider their unique tree paths. The paths from $a$ to $b$ and from $a$ to $c$ have an initial common segment ending at a vertex $m$. Beyond $m$ their tails are disjoint, because two distinct connecting routes would create a cycle. The union of those tails is therefore the unique path from $b$ to $c$. Hence \[ m\in T[a,b]\cap T[a,c]\cap T[b,c]. \] A connected path containing two vertices of a tree contains their unique connecting path. Since $Q_2$ contains $a,b$, it contains $T[a,b]$; the corresponding statements for $Q_1,Q_3$ show that all three contain $m$.

Combining this lemma with pairwise intersection proves the catalogue statement for every finite tree. The proof provides a witness from any three pairwise-intersection vertices; it does not assume a common endpoint or a common edge.

Another exact subclass and an obstruction to overextension.

If $G$ has a Hamiltonian path on $n$ vertices, then $L(G)=n-1$ and every longest path uses all $n$ vertices. In this traceable subclass the intersection of all longest-path vertex sets is $V(G)$, so the triple assertion also follows. This observation includes complete graphs and cycles, beyond the tree case.

However, pairwise intersection of arbitrary paths in a graph does not imply triple intersection. The three individual edges of a triangle are paths; their vertex sets meet pairwise and have empty total intersection. These paths are not longest, since the triangle has two-edge paths. Thus the example does not refute the target. It does refute the attempted inference that the tree Helly lemma holds in every graph simply because its objects are paths.

Verification and the first remaining gap.

The bridge-path concatenation uses genuinely disjoint $P,Q$ and a connector with disjoint interior; omitting either fact could create a repeated vertex. The tree median proof uses uniqueness of connecting paths, a property destroyed by cycles. These are separate ingredients: longestness produces pairwise intersection in any connected graph, while acyclicity upgrades it to triple intersection.

For a connected nontraceable graph with cycles, neither ingredient provided here supplies the missing upgrade. One must show that the special maximal lengths prohibit all configurations of three pairwise-intersecting paths with empty total intersection. The triangle's three edges explain the combinatorial possibility but do not meet the maximal-length constraint. No such exclusion or genuine longest-path counterexample is produced here.

Final status.

Pairwise intersection is proved generally; triple intersection is proved for trees and for graphs with Hamiltonian paths. The unrestricted three-longest-path problem is UNRESOLVED by this attempt. The conflicting literature signals were recorded explicitly rather than promoted to a solution claim.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3125 (OPG-46538), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Do any three longest paths in a connected graph have a vertex in common?. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/do_any_three_longest_paths_in_a_connected_graph_have_a_vertex_in_common.
• R1 N. Sarkar, Any Three Longest Paths In A Connected Graph Has A Common Vertex, arXiv:2006.16245 $2020$. Checked abstract contains a claimed proof; this attempt does not certify it. https://arxiv.org/abs/2006.16245.
• R2 J. Ma, B. Ning and Z. Zhao, Longest cycles intersect linearly in highly connected graphs, arXiv:2609.20724v1 (17 September 2026), Section 9.4, concluding problem. Checked full text still asks the three-path question. https://arxiv.org/html/2609.20724v1.