A new mathematical proof identifies the exact degree threshold needed to remove the vertices of a directed path from a strongly connected graph without breaking that connectivity. For every positive integer m, the result says that a strongly connected digraph with minimum semidegree at least m + 1 contains a directed path with m vertices whose deletion leaves the graph strongly connected.
The finding settles the k = 1 case of a conjecture associated with Mader. In plain terms, it covers the ordinary strong-connectivity setting: a network of one-way links contains a path with m vertices that can be removed while directed routes between the remaining parts are preserved. The paper also shows that the threshold cannot be reduced in general.
The conjecture behind the result
Mader’s conjecture asks whether every k-strong digraph with minimum semidegree at least 2k + m − 1 contains an order-m directed path whose vertex deletion leaves a k-strong digraph. For k = 1, that bound becomes m + 1, exactly the threshold proved in the new result.
A lower bound with no spare room
The threshold matters because the theorem is not merely an existence statement with a generous safety margin. The authors describe the advance as reducing an earlier bound of 2m to m + 1 for the k = 1 case. Their construction Dm,n shows why the new figure is sharp: for n ≥ 2, the constructed digraph is strongly connected while its minimum semidegree is only m.
The result applies to finite digraphs, meaning directed graphs, with no loops or parallel arcs. Arcs pointing in opposite directions between the same two vertices are allowed. Minimum semidegree sets a lower bound on the number of incoming and outgoing arcs at each vertex, while strong connectivity is the requirement that directed routes continue to link the graph.
How the proof searches for the path
The argument is deductive rather than statistical. It repeatedly uses an endpoint-counting lemma that requires only a minimum outdegree condition, then chooses what the paper calls an m-max pair: an order-m directed path together with a largest strongly connected component left after the path’s vertices are deleted.
That choice turns the problem into an extremal one. If no suitable path existed, the endpoint count and the selected largest remainder would force a contradiction. The result is therefore a universal guarantee over every finite digraph meeting the stated assumptions, not an estimate based on a sample of observed networks.
A second way to remove a path
The paper then turns vertex deletion into a related question: can the arcs of a directed path be removed while strong connectivity survives? For every integer m ≥ 2, it proves that a strongly connected digraph with minimum semidegree at least max{2, m − 1} contains an order-m directed path whose arc deletion leaves the graph strongly connected.
The construction behind this step uses distinct endpoints around the path and retains the remaining k-strong subdigraph after the path’s arcs are deleted. The authors also prove a broader conditional statement. For k ≥ 1 and m ≥ 3, if Mader’s vertex-deletion conjecture holds for k and m − 2, then every k-strong digraph with minimum semidegree at least 2k + m − 3 has an order-m path whose arc deletion leaves a k-strong digraph.
One special case is unconditional for every positive k: any k-strong digraph with minimum semidegree at least 2k contains an order-three directed path whose arc deletion leaves it k-strong. This extends the arc-deletion result beyond the k = 1 setting, but only for paths of that fixed order.
What remains open
The advance has a defined boundary. The main vertex-deletion theorem confirms only the k = 1 case, not the conjecture for arbitrary positive k and m. The general arc-deletion conjecture also remains unresolved outside the special cases proved here: k = 1 for arbitrary m, and order-three paths for all positive k.
These are theorem-level results in finite digraph theory. They do not report empirical data, statistical uncertainty or practical performance measures, and the guarantees apply only when the stated connectivity and minimum-semidegree assumptions hold. Whether the two conjectures are true for arbitrary positive k and m remains open.
The work is an arXiv preprint, version v1, dated 25 Aug 2026. Hojin Chu acknowledges a KIAS Individual Grant, while Boram Park acknowledges a National Research Foundation of Korea grant funded by the Korea government and Seoul National University’s New Faculty Startup Fund. The authors also declare using OpenAI’s GPT-5.6 Sol to explore proof refinements, check details and improve exposition, while saying that suggestions were independently verified and revised.
Paper data and sources
Original title: Connectivity keeping paths in digraphs
Authors: Hojin Chu, Boram Park, Homoon Ryu
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text