Generating strongly 2-connected digraphs

Evangelos Protopapas; Florian Reich; Giannos Stamoulis; Meike Hatzel; Sebastian Wiederrecht; Stephan Kreutzer

REVIEW 2 major objections 3 minor 1 cited by

Generating strongly 2-connected digraphs

T0 review · 2 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper establishes a directed splitter theorem: if $H$ is a butterfly-minor of $D$ and both are strongly 2-connected, then $D$ can be built from $H$ by a sequence of strong-2-connectivity-preserving augmentations of four fixed types.

desk verdict A serious and likely correct directed splitter theorem; the written proof has a few terse spots, but the stress-test concern about Lemma 4.2 does not hold up. read the letter →

arxiv 2411.09791 v1 pith:LT5XU2CH submitted 2024-11-14 math.CO

Meike Hatzel , Stephan Kreutzer , Evangelos Protopapas , Florian Reich , Giannos Stamoulis , Sebastian Wiederrecht This is my paper · ORCID

classification math.CO MSC 05C2005C4005C83

keywords strongly2-connecteddigraphsbutterfly-minorgenerationtheoremsplitterbracesearpathsaugmentations

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves a generation theorem for strongly 2-connected digraphs. Starting from the single digraph $A_4$ and all bidirected cycles $C_k$ with $k\geq 3$, every strongly 2-connected digraph can be built by repeatedly applying four local operations: basic, chain, collarette, and bracelet augmentations. The stronger, more general statement is a splitter theorem: whenever $H$ is a butterfly-minor of $D$ and both are strongly 2-connected, there is a sequence $D_0=H,\dots,D_n=D$ in which every intermediate digraph is strongly 2-connected and each step is one augmentation. A sympathetic reader should care because this is the directed analogue of ear decompositions for 2-connected graphs and of splitter theorems for 3-connected graphs, adapted to the butterfly-minor relation. The cost of the result is that one operation, the chain augmentation, can introduce arbitrarily many vertices in a single step; the paper argues this is unavoidable because the butterfly-minor order has infinite anti-chains built from bidirected paths.

What carries the argument

The argument is carried by ear paths inside an $H$-expansion, the subgraph of $D$ that models $H$ via a butterfly-model. An $H'$-ear path is a directed path that meets the expansion only at its endpoints, or a single missing edge between vertices of the expansion. The proof's engine is a trichotomy (Lemma 4.2): every such ear path is exactly augmenting, switching, or bad. Augmenting paths immediately yield a basic augmentation; switching paths run parallel to the model of an edge of $H$ and let the expansion be re-optimised by switching onto the path to obtain a new expansion; bad paths form a directed cycle with the in- and out-star of one modelled vertex and are handled by the concepts of blocking vertices and escapes, which force the existence of a path that can produce a chain or collarette augmentation. Laced paths, in which two paths intersect in a sequence of directed segments, supply the normal form that converts these configurations into the four concrete operations.

What would settle it

Lemma 4.2 claims that for every $H$-expansion $H'$ in a strongly 2-connected digraph $D$, every $H'$-ear path is exactly one of augmenting, switching, or bad. To test this, enumerate all ear paths in a small pair, for example $H$ equal to the bidirected triangle and $D$ a strongly 2-connected digraph on four or five vertices containing it as a butterfly-minor, and check each path against the augmenting conditions, the switching conditions, and the bad-path cycle condition. A single path that satisfies none of the three classes, or satisfies two, falsifies the trichotomy and with it the inductive step on which Theorem 1.2 rests.

Watch

Extended reading notes

Core claim

At the core is Theorem 1.2. Let $D$ and $H$ be strongly 2-connected digraphs with $H$ a butterfly-minor of $D$, meaning $H$ can be obtained from $D$ by deleting vertices and edges and contracting only edges that are the unique outgoing edge of their tail or the unique incoming edge of their head. The theorem asserts a sequence $D_0=H, D_1,\dots,D_n=D$ of strongly 2-connected digraphs in which each $D_i$ is obtained from $D_{i-1}$ by exactly one of four augmentations: adding an edge (possibly after splitting a vertex), weaving a directed path through an existing edge, subdividing the two edges of a digon and adding a path between the subdivision vertices, or piercing a two-edge path through a vertex of in- and out-degree two. Since the four augmentations preserve strong 2-connectivity, the sequence never leaves the class. Combined with the earlier fact that every strongly 2-connected digraph contains $A_4$ or a bidirected cycle as a butterfly-minor, this yields Theorem 1.1: the class generated from the base set $B_2$ consisting of $A_4$ and all bidirected cycles $C_k$ for $k\ge 3$ by the four augmentations is exactly the class of strongly 2-connected digraphs.

Load-bearing premise

The load-bearing premise is Lemma 4.2's classification: every ear path attached to a fixed $H$-expansion is exactly one of augmenting, switching, or bad; if some ear path escapes all three classes or fits more than one, the case analysis that turns ear paths into the four augmentations may miss a configuration and the induction step can fail.

Editorial extensions

If this is right

Every strongly 2-connected digraph can be synthesised from $A_4$ or a bidirected cycle by finitely many applications of the four augmentations (Theorem 1.1).
The intermediate graphs in such a generation or reduction sequence can be kept strongly 2-connected at every step, so no construction ever passes through a digraph that is only weakly connected or 1-connected (Theorem 1.4).
Because the chain augmentation can add arbitrarily many vertices at once, the four operations cover the classical ear-decomposition of 2-connected undirected graphs: an undirected ear is emulated by a chain followed by a basic augmentation.
The base family must be infinite, containing all bidirected cycles, which reflects that the butterfly-minor order has infinite anti-chains; the unbounded chain augmentation is exactly the mechanism that navigates between members of such anti-chains.
Theorem 1.2 gives, in principle, a reduction mechanism: any strongly 2-connected butterfly-minor $H$ of $D$ can be enlarged back to $D$ one strong-2-connectivity-preserving augmentation at a time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper: the proof is constructive enough to suggest an explicit algorithm that, given $D$ and $H$, outputs the augmentation sequence; the paper does not analyse running time, but the case analysis indicates that the switching and escape searches are the steps to make efficient.
Beyond the paper: the same ear-path trichotomy might transfer to other directed minor relations, such as directed topological minors or higher strong connectivity, once the appropriate analogue of a bad path is identified, yielding splitter theorems for those settings.
Beyond the paper: the paper's diagnosis that bidirected paths are the only obstruction to well-quasi-ordering suggests a testable stronger claim: every butterfly-minor-closed class of strongly 2-connected digraphs that forbids arbitrarily long bidirected paths should be well-quasi-ordered.
Beyond the paper: because the chain augmentation is the only operation that adds unboundedly many vertices, a natural test extension is to ask which subclasses of strongly 2-connected digraphs can be generated using only basic, collarette, and bracelet augmentations.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my take. The paper proves a directed analogue of Seymour's splitter theorem for strongly 2-connected digraphs under butterfly-minors, with a sequence built from four augmentations. That is genuinely new and is the kind of structural result that should anchor future work on digraph connectivity and minors. The proof is long but organized: the ear-path trichotomy (augmenting, bad, switching) is a real organizing idea, and the four augmentation types (basic, chain, collarette, bracelet) are forced by examples like the anti-chain discussion. The paper is also honest about McCuaig's unpublished claim and does not hide the reliance on Wiederrecht's base-minor theorem. I checked the main soft spot flagged in the stress-test. Lemma 4.2's 'Thus Sin_u ∪ Sout_u ∪ P ... are acyclic' is indeed too fast. But the conclusion is still right: a switching path with respect to (u,v) has endpoints in Sout_u ∪ Sin_v; if it were bad at u, both endpoints would have to lie in Sout_u, and the return path required for a cycle would also be in Sout_u, hence in [S3]'s acyclic set. The same works for v, and for other branchsets the endpoint sets are disjoint. So the trichotomy holds, but the write-up should spell this out rather than hand-wave with 'Thus.' That is a minor presentation issue, not a load-bearing flaw. The other soft spot is Theorem 1.4: the proof that the four augmentations preserve strong 2-connectivity is more of a sketch, especially for chain, collarette, and bracelet. The claims about the set W and the path extensions are plausible but not fully verified in the text. This is worth tightening in revision, but it does not undermine the main theorem. The main theorem's proof is inductive and depends on the lemmas in Sections 5-7. I did not find circularity; the use of [Wie20] is a coauthor citation but the result is published and independent enough. No free parameters, no invented entities, and the description of the base B2 is clean. Bottom line: this is a paper for structural graph theorists, especially people working on directed minors and connectivity. It deserves a serious referee. With the terse spots cleaned up, it should be accepted. Recommendation: send to peer review, and in the report ask for a fuller justification of the Lemma 4.2 disjointness and a more detailed proof of Theorem 1.4.

Referee Report

2 major / 3 minor

Summary. The paper proves a splitter/generation theorem for strongly 2-connected digraphs under the butterfly-minor relation. The main result (Theorem 1.2) states that whenever H is a strongly 2-connected butterfly-minor of a strongly 2-connected digraph D, there is an interpolation sequence from H to D in which each intermediate digraph is strongly 2-connected and each step is one of four local augmentations: basic, chain, collarette, or bracelet. Combined with Wiederrecht's theorem that every strongly 2-connected digraph contains a member of the base family B2 as a butterfly-minor, this yields a generative description of all strongly 2-connected digraphs from B2 (Theorem 1.1). The proof is by induction on |E(D)|-|E(H)|, with the induction step reduced to showing that every H-expansion in D contains a subgraph that is an expansion of an H-augmentation; the central technical device is a classification of ear paths into augmenting, bad, and switching paths.

Significance. If the main theorem is correct, this is a substantial structural result: a splitter theorem for strongly 2-connected digraphs in the butterfly-minor order, with a concise explicit base family and four fairly local operations. The paper clearly explains why an operation adding an unbounded number of vertices in one step is unavoidable, namely the existence of infinite anti-chains of bidirected paths under butterfly-minors. The proof is modular and carefully organized, with many auxiliary lemmas, and the reliance on Wiederrecht's published base-minor theorem is explicit. However, the present version contains a genuine gap in the proof of the ear-path trichotomy (Lemma 4.2); this must be repaired before the proof can be accepted as written.

major comments (2)

[§4.1, Lemma 4.2] The disjointness part of the trichotomy is not proved. The text claims that for an H′-switching path P with respect to (u,v), condition [S3] implies that S^in_u ∪ S^out_u ∪ P and S^in_v ∪ S^out_v ∪ P are acyclic. For u≠v this implication is false: the digraph in [S3] contains S^out_u and S^in_v but omits S^in_u and S^out_v. A path P with start(P)∈S^out_u and end(P)∈R_u can satisfy [S1]–[S3] while P together with the path end(P)→root in S^in_u and root→start(P) in S^out_u forms a directed cycle, making P simultaneously switching and bad. Thus the assertion that every ear path is exactly one of the three types is not established. This is load-bearing because later arguments, such as the case split in the proof of Lemma 6.4 and the classification of ear paths in Case 5 of Theorem 1.2, read Lemma 4.2 as an exclusive dichotomy. The authors should either provide a correct proof of exclusivity or weaken the lemma to an inclusive classification and re-verify all later uses of the dichotomy.
[§3.3, Theorem 1.4] The proof that the four augmentations preserve strong 2-connectivity is too compressed in the collarette case. The sentence 'Observe that, since D is strongly 2-connected and |V(D)|≥4, we can guarantee that the vertices in W have the required property' is not a proof: one needs a case analysis showing that each vertex in W, including the internal vertices of the added chain, has two vertex-disjoint paths to and from V(D*)\W. The subsequent claim that failure of this property forces u and v to have the same unique out-neighbour is not obvious and is not justified. Since Theorem 1.4 is needed to ensure that every intermediate digraph in the sequence of Theorem 1.2 is strongly 2-connected, this argument should be expanded.

minor comments (3)

[§3.3, proof of Theorem 1.4, chain case] The displayed list of possible edges contains '(e(u),b(v))' twice and should list the four distinct edges {(b(u),b(v)), (b(u),e(v)), (e(u),b(v)), (e(u),e(v))}.
[§7, Case 5, Claim 1] The inference 'by (4), neither O nor I is non-parallel switching. Thus ... end(O)∉V(Sin_w)...' should be expanded: it relies on the fact that H′ is a subdivision of H in this case, so an internal vertex of Q has exactly one outgoing and one incoming edge in H′, and therefore an ear path starting there and ending in Sin_w for w≠u would indeed be non-parallel switching rather than parallel switching. This point is currently implicit.
[§3.4, Figure 6] The abbreviations 'exp.' and 'aug.' in the caption of Figure 6 are not defined in the caption; please spell them out or refer to the surrounding text.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the main theorem is an independent induction over explicitly defined augmentations; the only self-citation (Wiederrecht's base-minor theorem) is a published external result used only to supply the starting base, not an input-output loop.

full rationale

The paper's central claim, Theorem 1.2, is proved by induction on |E(D)|-|E(H)|: each inductive step isolates a strongly 2-connected H-augmentation K that is a butterfly-minor of D, via a case analysis on ear paths (augmenting, bad, switching), and then applies the induction hypothesis to D and K. The four augmentation types are defined in Section 3.1 independently of the conclusion, and Theorem 1.4 (augmentations preserve strong 2-connectivity) is proved directly from the strong 2-connectivity of D. The absolute generation statement, Theorem 1.1, uses Theorem 1.3 from Wiederrecht [Wie20] to obtain a starting member of B2 inside any strongly 2-connected digraph. Although Wiederrecht is a coauthor of the present paper, [Wie20] is a published, externally checkable theorem that does not assume Theorem 1.1 or 1.2; it supplies only the initial base minor and is not equivalent to the target generation sequence. Likewise, Lemma 2.1 is cited to [AKKW16] for the butterfly-model characterization; it is a standard external equivalence and not an input to the main theorem. The reviewer-flagged issue in Lemma 4.2 — that the acyclicity condition [S3] may not imply acyclicity of Sin_v ∪ Sout_v ∪ P when u≠v — concerns whether the 'exactly one' trichotomy proof is complete; that is a potential correctness gap, not a circularity, because the switching/bad/augmenting categories are not defined in terms of the theorem's conclusion. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled in via citation. The note that McCuaig's analogous result is an unpublished manuscript is a stated limitation, but the present proof does not depend on that manuscript. Overall, the derivation chain is self-contained apart from normal external theorems, so no circular step is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no free parameters in the sense of fitted constants. Its central claim rests on standard definitions plus one external theorem, Wiederrecht's base-minor theorem, cited from the literature. The four augmentation operations are defined explicitly, not inferred from data. No new entities are postulated; the technical concepts (ear paths, escapes, blocking vertices, laced paths) are proof devices, not additional assumptions.

assumptions (4)

domain assumption Finite simple digraphs are the object of study.
Section 2 defines the scope; all results are stated for finite simple digraphs.
standard math H is a butterfly-minor of D if and only if H has a butterfly-model in D.
Lemma 2.1, quoted from [AKKW16], is used throughout to work with models instead of contraction sequences.
domain assumption Every strongly 2-connected digraph contains a member of B2 as a butterfly-minor.
Theorem 1.3 in the introduction, cited from [Wie20]; it is the bridge from Theorem 1.2 to the generation theorem Theorem 1.1.
standard math The directed ear-decomposition theorem for strongly connected digraphs holds.
Used in the introduction (Section 1) as a motivating reformulation and as a building block for the chain augmentation reasoning.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Generating strongly 2-connected digraphs." pith.science (2026). https://pith.science/paper/LT5XU2CH

@misc{pith2026241109791,
  author       = {Pith},
  title        = {Pith review of: Generating strongly 2-connected digraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LT5XU2CH}},
  note         = {Machine review of arXiv:2411.09791}
}

abstract

We prove that there exist four operations such that given any two strongly $2$-connected digraphs $H$ and $D$ where $H$ is a butterfly-minor of $D$, there exists a sequence $D_0,\dots, D_n$ where $D_0=H$, $D_n=D$ and for every $0\leq i\leq n-1$, $D_i$ is a strongly $2$-connected butterfly-minor of $D_{i+1}$ which is obtained by a single application of one of the four operations. As a consequence of this theorem, we obtain that every strongly $2$-connected digraph can be generated from a concise family of strongly $2$-connected digraphs by using these four operations.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Unavoidable butterfly minors in digraphs of large cycle rank
math.CO 2025-07 accept novelty 8.0 of 10

Every digraph of sufficiently large cycle rank contains a directed ladder, a directed cycle chain, or a directed tree chain of order k as a butterfly minor.

Reference graph

Works this paper leans on

15 extracted references · 6 canonical work pages · cited by 1 Pith paper

[1]

T he E rdos- P \'o sa property for directed graphs

Saeed Akhoondian Amiri, Ken-ichi Kawarabayashi, Stephan Kreutzer, and Paul Wollan. T he E rdos- P \'o sa property for directed graphs. arXiv preprint arXiv:1603.02504 , 2016

arXiv 2016
[2]

Barnette and Branko Gr\" u nbaum

David W. Barnette and Branko Gr\" u nbaum. On S teinitz's theorem concerning convex 3 -polytopes and on some properties of planar graphs. In The M any F acets of G raph T heory ( P roc. C onf., W estern M ich. U niv., K alamazoo, M ich., 1968) , pages 27--40. Springer, Berlin, 1969

work page 1968
[3]

Matchings, matroids and unimodular matrices

James Ferdinand Geelen. Matchings, matroids and unimodular matrices . ProQuest LLC, Ann Arbor, MI, 1996. Thesis (Ph.D.)--University of Waterloo (Canada). URL: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:NN09343

work page 1996
[4]

Circle graph obstructions under pivoting

Jim Geelen and Sang-il Oum. Circle graph obstructions under pivoting. J. Graph Theory , 61(1):1--11, 2009. https://doi.org/10.1002/jgt.20363 doi:10.1002/jgt.20363

doi:10.1002/jgt.20363 2009
[5]

C. H. C. Little. A characterization of convertible (0,1)-matrices. J. Combinatorial Theory Ser. B , 18:187--208, 1975. https://doi.org/10.1016/0095-8956(75)90048-9 doi:10.1016/0095-8956(75)90048-9

doi:10.1016/0095-8956(75)90048-9 1975
[6]

Matching structure and the matching lattice

L\' a szl\' o Lov\' a sz. Matching structure and the matching lattice. J. Combin. Theory Ser. B , 43(2):187--222, 1987. https://doi.org/10.1016/0095-8956(87)90021-9 doi:10.1016/0095-8956(87)90021-9

doi:10.1016/0095-8956(87)90021-9 1987
[7]

Brace generation

William McCuaig. Brace generation. J. Graph Theory , 38(3):124--169, 2001. https://doi.org/10.1002/jgt.1029 doi:10.1002/jgt.1029

work page doi:10.1002/jgt.1029 2001
[8]

Paths and topological minors in directed and undirected graphs

Irene Muzi. Paths and topological minors in directed and undirected graphs . PhD thesis, Ph. D. Dissertation, Sapienza Universita Di Roma, 2017

2017

Show all 15 references

[9]

Generating bricks

Serguei Norine and Robin Thomas. Generating bricks. J. Combin. Theory Ser. B , 97(5):769--817, 2007. https://doi.org/10.1016/j.jctb.2007.01.002 doi:10.1016/j.jctb.2007.01.002

2007 doi
[10]

P. D. Seymour. Decomposition of regular matroids. J. Combin. Theory Ser. B , 28(3):305--359, 1980. https://doi.org/10.1016/0095-8956(80)90075-1 doi:10.1016/0095-8956(80)90075-1

1980 doi
[11]

Characterization of even directed graphs

Paul Seymour and Carsten Thomassen. Characterization of even directed graphs. J. Combin. Theory Ser. B , 42(1):36--45, 1987. https://doi.org/10.1016/0095-8956(87)90061-X doi:10.1016/0095-8956(87)90061-X

1987 doi
[12]

V.K. Titov. A constructive description of some classes of graphs . PhD thesis, Moscow, 1975

1975
[13]

W. T. Tutte. A theory of 3 -connected graphs. Nederl. Akad. Wetensch. Proc. Ser. A 64 = Indag. Math. , 23:441--455, 1961

1961
[14]

Non-separable and planar graphs

Hassler Whitney. Non-separable and planar graphs. Trans. Amer. Math. Soc. , 34(2):339--362, 1932. https://doi.org/10.2307/1989545 doi:10.2307/1989545

1932 doi
[15]

Digraphs of directed treewidth one

Sebastian Wiederrecht. Digraphs of directed treewidth one. Discrete Math. , 343(12):112124, 9, 2020. https://doi.org/10.1016/j.disc.2020.112124 doi:10.1016/j.disc.2020.112124

2020

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

T he E rdos- P \'o sa property for directed graphs

Saeed Akhoondian Amiri, Ken-ichi Kawarabayashi, Stephan Kreutzer, and Paul Wollan. T he E rdos- P \'o sa property for directed graphs. arXiv preprint arXiv:1603.02504 , 2016

arXiv 2016

[2] [2]

Barnette and Branko Gr\" u nbaum

David W. Barnette and Branko Gr\" u nbaum. On S teinitz's theorem concerning convex 3 -polytopes and on some properties of planar graphs. In The M any F acets of G raph T heory ( P roc. C onf., W estern M ich. U niv., K alamazoo, M ich., 1968) , pages 27--40. Springer, Berlin, 1969

work page 1968

[3] [3]

Matchings, matroids and unimodular matrices

James Ferdinand Geelen. Matchings, matroids and unimodular matrices . ProQuest LLC, Ann Arbor, MI, 1996. Thesis (Ph.D.)--University of Waterloo (Canada). URL: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:NN09343

work page 1996

[4] [4]

Circle graph obstructions under pivoting

Jim Geelen and Sang-il Oum. Circle graph obstructions under pivoting. J. Graph Theory , 61(1):1--11, 2009. https://doi.org/10.1002/jgt.20363 doi:10.1002/jgt.20363

doi:10.1002/jgt.20363 2009

[5] [5]

C. H. C. Little. A characterization of convertible (0,1)-matrices. J. Combinatorial Theory Ser. B , 18:187--208, 1975. https://doi.org/10.1016/0095-8956(75)90048-9 doi:10.1016/0095-8956(75)90048-9

doi:10.1016/0095-8956(75)90048-9 1975

[6] [6]

Matching structure and the matching lattice

L\' a szl\' o Lov\' a sz. Matching structure and the matching lattice. J. Combin. Theory Ser. B , 43(2):187--222, 1987. https://doi.org/10.1016/0095-8956(87)90021-9 doi:10.1016/0095-8956(87)90021-9

doi:10.1016/0095-8956(87)90021-9 1987

[7] [7]

Brace generation

William McCuaig. Brace generation. J. Graph Theory , 38(3):124--169, 2001. https://doi.org/10.1002/jgt.1029 doi:10.1002/jgt.1029

work page doi:10.1002/jgt.1029 2001

[8] [8]

Paths and topological minors in directed and undirected graphs

Irene Muzi. Paths and topological minors in directed and undirected graphs . PhD thesis, Ph. D. Dissertation, Sapienza Universita Di Roma, 2017

2017