Lovász Removable-Path Conjecture for Three Prescribed Vertices

Definitions and mathematical statement

Use finite simple graphs. A graph is $r$-connected if it has more than $r$ vertices and deleting fewer than $r$ vertices leaves it connected. The intended three prescribed vertices must be pairwise distinct: if $x=s$ or $x=t$, the demanded vertex disjointness would be impossible. This distinctness is implicit in "three vertices" but not expanded in the extracted formula.

The source asks whether there is a finite-valued function $f_3:{\mathbb{Z}}_{\geq1}\to{\mathbb{Z}}_{\geq1}$ such that for every $k\geq1$, every $f_3(k)$-connected graph $G$, and every pairwise distinct $s,t,x\in V(G)$, there exist a simple $s$-to-$t$ path $P$ and a $k$-connected subgraph $H\leq G$ satisfying \[ x\in V(H),\qquad V(H)\cap V(P)=\varnothing. \] Equivalently, $G-V(P)$ must contain a $k$-connected subgraph through $x$. The deleted vertices include the endpoints of $P$. The whole remainder $G-V(P)$ is not required by the displayed statement to be $k$-connected. No path length, size of $H$, or growth-rate bound on $f_3$ is specified. The connectivity threshold depends only on $k$, not on $G$ or the chosen vertices.

The supplied literature assessment checked 2026-08-21 relates this to Lovász's removable-path question, distinguishes a solved edge-removal weakening from a remaining vertex-deletion problem, and reports the latter open for general $k$. It does not reproduce a theorem identifying the present subgraph-through-$x$ statement with the stronger condition that the entire remainder be $k$-connected. Nor would edge deletion alone establish the required vertex disjointness. The precise relationship and special-case hypotheses must be checked rather than strengthening the extracted conclusion.

Short English statement

Is sufficiently high connectivity, depending only on $k$, enough to find a path between two prescribed vertices disjoint from a $k$-connected subgraph through a third? The vertices must be distinct, and the source asks for a subgraph of the remainder rather than connectivity of the whole remainder.

Sources

• Local UnsolvedMath registry, permanent ID 30000726, catalogue entry, Lovász Removable-Path Conjecture for Three Prescribed Vertices; the original wording labels it Lovász-related.
• Graph Theory (2008), Oberwolfach Reports, pp. 887--944, DOI https://doi.org/10.4171/owr/2007/16.
• Supplied reference "weaker Lovasz path-removal result": https://doi.org/10.1016/j.jctb.2007.11.003.
• Supplied literature triage checked 2026-08-21; no exact reduction or equivalence with the original removable-path statement is reproduced.