REVIEW 4 minor 7 references
Avoidable paths in graphs
T0 review · 0 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For every positive integer k, every graph that contains an induced path on k vertices also contains an avoidable path on k vertices.
desk verdict Solid proof of a genuine conjecture about avoidable induced paths; the only compressed step is a valid but unwritten case split. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central device is the merging operation: given an edge u1u2, form G' by identifying u1 and u2 into a single vertex u with neighbourhood N({u1,u2}). Lemma 2.3 shows that if the refined property HR holds in the smaller merged graph, then HR passes back to the original graph at u1. That transfer step is the engine of the proof: an induced cycle through the merged vertex is turned into an induced cycle in the original graph by replacing u with u1, u2, or the edge u1u2 'as appropriate'. The induction then runs on a minimal counterexample, and two short claims force every induced P_k in the residual graph to dominate the relevant neighbourhood, producing the contradiction.
What would settle it
Find a graph G and edge u1u2 such that the merged graph G' has an induced cycle through the merged vertex u whose preimage under every one of the three replacements (u1 alone, u2 alone, or the edge u1u2) has a chord. Such an example would break Lemma 2.3 and with it the induction that proves Theorem 1.9.
Extended reading notes
Core claim
The paper establishes Theorem 1.9: for every positive integer k, every graph that contains an induced P_k (an induced path on k vertices) also contains an avoidable P_k, where a path is avoidable when it is induced and every induced extension of it lies in an induced cycle. The proof goes through a stronger statement, property HR(G,k,u): for every graph G and vertex u, either G - N[u] contains no induced P_k, or G contains an avoidable P_k wholly inside G - N[u]. This stronger form is what makes the induction go through, and it also yields corollaries about finding two avoidable paths that are non-adjacent.
Load-bearing premise
The load-bearing step is Lemma 2.3's assertion that an induced cycle through the merged vertex can always be converted back to an induced cycle in the original graph by replacing the merged vertex with one endpoint, the other endpoint, or the edge between them, without creating a chord.
Editorial extensions
If this is right
- If G has an induced P_k avoiding a connected induced subgraph G[X] (i.e. in G - N[X]), then an avoidable P_k of G can be found there (Corollary 1.10).
- If G contains two non-adjacent induced P_k, then it contains two non-adjacent avoidable P_k (Corollary 1.11).
- The proof yields an explicit algorithm for finding an avoidable P_k in O(n^{k+2}) time, and the paper notes this is the best order of magnitude one can expect under the Exponential Time Hypothesis, because finding an induced P_k itself is W[1]-hard parameterised by k.
- The natural analogue for disjoint paths fails: for every k >= 3 there is a graph with two disjoint induced P_k but no two disjoint avoidable P_k.
Reading between the lines
- The same merging trick may transfer avoidability for other induced substructures whose extensions are paths, such as trees of fixed size, though the 'as appropriate' replacement step would need a new justification for branching shapes.
- Corollary 1.10 gives a constructive handle on separator-based decompositions: repeatedly prune closed neighbourhoods to extract several mutually avoiding paths, which could be useful in graph-colouring or domination arguments.
- The O(n^{k+2}) algorithm may be practical for small k (k=3,4) in sparse graphs, and could likely be improved by using faster algorithms for detecting induced paths in special graph classes, since the reduction step only calls InducedPath on subgraphs.
- One untested direction is whether the graph family form of Question 4.1 has a positive answer if the family contains trees beyond paths; the paper's counterexample suggests that cycle structure, not just path structure, drives avoidability.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves the conjecture of Beisegel et al. that for every positive integer k, every graph containing an induced path on k vertices also contains an avoidable induced path on k vertices. The proof is by minimal counterexample, using a strengthened induction hypothesis HR that asks for an avoidable P_k in G - N[u] whenever this induced subgraph contains a P_k. The central technical step is Lemma 2.3, which transfers HR from a graph obtained by merging an edge u_1u_2 into a vertex u back to the original graph. The authors also derive corollaries on multiple avoidable paths, exhibit a family of graphs showing that the analogous statement for two disjoint avoidable P_k fails for k >= 3, and give an O(n^{k+2}) algorithm based on the proof.
Significance. The result settles an open conjecture and unifies earlier work on avoidable vertices, avoidable edges, and the cycle-restricted theorem of Chvátal et al. The proof is elementary, self-contained, and the strengthened induction hypothesis is a clean and reusable idea. The explicit algorithm is a useful bonus, and its O(n^{k+2}) running time is plausibly best possible under ETH because it already must detect an induced P_k. The counterexample to the disjoint analogue sharpens the boundary of what can be expected from such theorems.
minor comments (4)
- [Section 2, Lemma 2.3] The sentence "By replacing u with either u1, u2 or the edge u1u2 as appropriate" is the only place where the proof asks the reader to supply a nontrivial case split that is load-bearing for Claim 2.6 and Theorem 2.4. Please spell out the two cases: either some u_i is adjacent to both neighbours of u on the induced cycle C, in which case u_i closes the cycle directly, or the two preimages are distinct singletons, in which case the edge u_1u_2 closes the cycle. In both cases no chord is introduced, because any extra edge would create an adjacency from u to a non-neighbour on C in G'.
- [Title and abstract] The title page has "A voidable paths in graphs" and the abstract has "A voidability"; these should be "Avoidable paths" and "Avoidability", respectively.
- [Section 3, complexity analysis] The recurrence R(n) <= n·n^k + max(R(n-1), B(n-2)) omits the case where u is isolated, in which case the call to FindAvoidablePath(G - N[u], k) is on a graph with n-1 vertices. The correct bound is max(R(n-1), B(n-1)), and the stated O(n^{k+2}) conclusion is unchanged.
- [Section 3, Algorithm 1] The correctness of the algorithm is stated only informally as following from the proof of Theorem 2.4. A short explicit invariant describing what FindAvoidablePathRefined(G, k, u) guarantees when HR(G, k, u) holds would make the algorithm verifiable, especially since the recursion can return a P_k found in a proper induced subgraph.
Circularity Check
No significant circularity: the proof derives the avoidable-P_k theorem from definitions by a minimal-counterexample induction, with no fitted inputs or load-bearing self-citations.
full rationale
The derivation chain is self-contained. Theorem 1.9 is obtained from Theorem 2.4, which asserts both HB(G,k) and HR(G,k) for every graph by induction on the number of vertices. The refined property HR(G,k,u) is defined independently of the conclusion: it says that either G-N[u] is P_k-free or there is an avoidable P_k of G in G-N[u]. The induction uses a minimal counterexample G, and the lemmas then derive contradictions using only graph-theoretic facts, not any fitted quantity or externally imposed normalization. Lemma 2.3, the most compressed step, transfers HR from a merged graph G' back to G. The paper's phrase 'By replacing u with either u1, u2 or the edge u1u2 as appropriate' is terse but is a genuine case split rather than a circular identification: for an induced cycle C in G' containing u, with neighbours a and b on C, either some ui is adjacent to both a and b and inserting ui closes the cycle, or the preimage neighbours are distinct vertices accommodated by the edge u1u2; any extra chord would have been a chord in G' through u, contradicting that C is induced in G'. Thus the unexpanded step is valid and not equivalent to the target statement by construction. The paper does not fit parameters and then relabel them as predictions; it does not invoke a uniqueness theorem from the authors' prior work to force its induction hypothesis; and its citations to Beisegel et al. and Chvátal et al. are contextual or superseded by the new elementary proof, with the paper explicitly stating that the proof is self-sufficient. No load-bearing self-citation chain appears. Therefore the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (3)
- domain assumption Graphs are finite, simple, and loopless.
- standard math Well-founded induction on the number of vertices is valid.
- standard math Subpaths of induced cycles are induced paths.
Cite this review
Pith. "Pith review of Avoidable paths in graphs." pith.science (2026). https://pith.science/paper/YFQSJFA5
@misc{pith2026190803788,
author = {Pith},
title = {Pith review of: Avoidable paths in graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/YFQSJFA5}},
note = {Machine review of arXiv:1908.03788}
}
read the original abstract
We prove a recent conjecture of Beisegel et al. that for every positive integer k, every graph containing an induced P_k also contains an avoidable P_k. Avoidability generalises the notion of simpliciality best known in the context of chordal graphs. The conjecture was only established for k in {1,2} (Ohtsuki et al. 1976, and Beisegel et al. 2019, respectively). Our result also implies a result of Chv\'atal et al. 2002, which assumed cycle restrictions. We provide a constructive and elementary proof, relying on a single trick regarding the induction hypothesis. In the line of previous works, we discuss conditions for multiple avoidable paths to exist.
Figures
Reference graph
Works this paper leans on
-
[1]
Vertex elimination orderings for hereditary graph classes
Pierre Aboulker, Pierre Charbit, Nicolas Trotignon, and Kristina Vu s kovi \'c . Vertex elimination orderings for hereditary graph classes. Discrete Mathematics , 338(5):825--834, 2015
work page 2015
-
[2]
Separability generalizes D irac's theorem
Anne Berry and Jean-Paul Bordat. Separability generalizes D irac's theorem. Discrete Applied Mathematics , 84(1-3):43--53, 1998
work page 1998
-
[3]
Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich, Martin Milani c , and Mary Servatius. Avoidable vertices and edges in graphs. In Zachary Friggstad, J \"o rg-R \"u diger Sack, and Mohammad R Salavatipour, editors, Algorithms and Data Structures , pages 126--139, Cham, 2019. Springer International Publishing
work page 2019
-
[4]
Marek Cygan, Fedor V Fomin, ukasz Kowalik, Daniel Lokshtanov, D \'a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized algorithms . Springer, 2015
work page 2015
- [5]
-
[6]
Gabriel Andrew Dirac. On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universit \"a t Hamburg , 25(1):71--76, 1961
work page 1961
-
[7]
Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
Tatsuo Ohtsuki, Lap Kit Cheung, and Toshio Fujisawa. Minimal triangulation of a graph and optimal pivoting order in a sparse matrix. Journal of Mathematical Analysis and Applications , 54(3):622--633, 1976
work page 1976
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.