Unavoidable substructures in large and infinite $2$-edge-connected graphs

M. N. Ellingham; Sarah Allred

arxiv: 2503.21574 · v4 · pith:B2VHXCG5new · submitted 2025-03-27 · 🧮 math.CO

Unavoidable substructures in large and infinite 2-edge-connected graphs

Sarah Allred , M. N. Ellingham This is my paper

Pith reviewed 2026-05-22 22:29 UTC · model grok-4.3

classification 🧮 math.CO

keywords unavoidable induced subgraphs2-edge-connected graphsinfinite graphsladdersminorsEulerian subgraphsmultigraphstopological minors

0 comments

The pith

Every large or infinite 2-edge-connected graph contains one of a specific list of induced subgraphs that includes chains of pinched super-clean ladders.

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

The paper determines the unavoidable induced subgraphs that must appear in any sufficiently large 2-edge-connected graph, whether finite or infinite. It identifies chains of pinched super-clean ladders as the new structures required in this connectivity class, which is weaker than 2-connected but stronger than merely connected. These structures are inserted into the known list from 2-connected graphs to produce a complete unavoidable set. The work yields corollaries for other types of subgraphs and extends to multigraphs when appropriate.

Core claim

We prove the existence of ubiquitous structures in 2-edge-connected graphs known as chains of pinched super-clean ladders, and incorporate these into a presentation of the unavoidable large induced subgraphs for large and infinite 2-edge-connected graphs. As consequences we obtain results on unavoidable large subgraphs, topological minors, minors, induced topological minors, induced minors, and Eulerian subgraphs in large and infinite 2-edge-connected graphs. When appropriate we extend our results to multigraphs.

What carries the argument

chains of pinched super-clean ladders, the new unavoidable induced structures that appear in the 2-edge-connected setting but are not forced by weaker connectivity.

If this is right

A complete list of unavoidable large subgraphs holds for 2-edge-connected graphs.
Unavoidable topological minors, minors, induced topological minors, and induced minors exist in the same setting.
Unavoidable Eulerian subgraphs must appear in large 2-edge-connected graphs.
All listed results extend to multigraphs and to infinite graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The insertion technique used here could be tested on other intermediate connectivity classes, such as graphs with minimum degree two.
The ladder chains may provide a route to new results on cycle double covers or other Eulerian properties in bridgeless graphs.
The unavoidable list could be used to derive bounds on the size of induced-subgraph-free families within the 2-edge-connected graphs.

Load-bearing premise

The unavoidable set already known for 2-connected graphs can be extended to 2-edge-connected graphs simply by adding the ladder-chain structures without extra connectivity assumptions or new case distinctions.

What would settle it

An arbitrarily large 2-edge-connected graph containing none of the listed induced subgraphs, including no chain of pinched super-clean ladders, would falsify the claim.

Figures

Figures reproduced from arXiv: 2503.21574 by M. N. Ellingham, Sarah Allred.

**Figure 1.1.** Figure 1.1: Structure of Θ∞ For several graph classes below we use the operation of replacing a vertex by a triangle: if v has degree d ≤ 3 and neighbors ui , 1 ≤ i ≤ d, we delete v, add a triangle of new vertices (v1v2v3), and add edges uivi for 1 ≤ i ≤ d. We use certain fan-like structures. Let F∞ denote the graph that consists of a vertex u, a ray v1v2v3 . . . (called the rim), and edges uvi for all i ∈ {1, 2, 3,… view at source ↗

**Figure 1.2.** Figure 1.2: Two types of fan-like structure Note that the labeling of vertices in Figures 1.2(a) and 1.2(b) will be used in Section 3. We also need ladder-like structures, illustrated in [PITH_FULL_IMAGE:figures/full_fig_p004_1_2.png] view at source ↗

**Figure 1.** Figure 1: (b) [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗

**Figure 1.3.** Figure 1.3: Ladder-like structures Theorem 1.8 ([2, (1.7)]). Every infinite 2-connected graph contains K∞, an infinite slim ladder, or a member of Θ∞ ∪ F∞ ∪ F ∆ ∞ ∪ L∞ ∪ L ∆ ∞ ∪ L ∇∆ ∞ as an induced subgraph. As shown in [2], Theorem 1.7 on finite graphs can also be proved using Theorem 1.8 on infinite graphs. In Ramsey-type theorems, we want the list of unavoidable graphs (except complete graphs) to be minimal in t… view at source ↗

**Figure 1.4.** Figure 1.4: Graphs from Theorem 1.9 clean pinched ladder is a pinched ladder in which all crosses and embedded fans are trivial. See [PITH_FULL_IMAGE:figures/full_fig_p006_1_4.png] view at source ↗

**Figure 1.5.** Figure 1.5: A chain of 5 super-clean pinched ladders [PITH_FULL_IMAGE:figures/full_fig_p006_1_5.png] view at source ↗

**Figure 1.6.** Figure 1.6: Graphs from Theorem 1.10 Our second main result is the following. Theorem 1.10. Every infinite 2-edge-connected graph contains one of the following as an induced subgraph: K∞, an ∞-flower, a one-way infinite chain of finite super-clean pinched ladders, a one-way infinite superclean pinched ladder, or a member of the family Θ∞ ∪ L∞ ∪ L ∆ ∞ ∪ L ∇∆ ∞ . In Sections 2 and 3, we prove Theorems 1.9 and 1.10, r… view at source ↗

**Figure 1.** Figure 1: (a) [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗

read the original abstract

In 1930, Ramsey proved that every large graph contains either a large clique or a large edgeless graph as an induced subgraph. It is well known that every large connected graph contains a long path, a large clique, or a large star as an induced subgraph. Recently Allred, Ding, and Oporowski presented the unavoidable large induced subgraphs for large and infinite $2$-connected graphs. The $2$-edge-connected (sometimes called bridgeless) graphs form an important class between connected graphs and $2$-connected graphs. In this paper we describe the unavoidable large induced subgraphs for large and infinite $2$-edge-connected graphs. Ubiquitous structures in $2$-edge-connected graphs that we call `chains of pinched super-clean ladders' play an important role in these descriptions. As consequences we obtain results on unavoidable large subgraphs, topological minors, minors, induced topological minors, induced minors, and Eulerian subgraphs in large and infinite $2$-edge-connected graphs. When appropriate we extend our results to multigraphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Extends unavoidable induced subgraphs from 2-connected to 2-edge-connected graphs by proving chains of pinched super-clean ladders are unavoidable and folding them into the list.

read the letter

This paper takes the Allred-Ding-Oporowski result on unavoidable induced subgraphs in large and infinite 2-connected graphs and adapts it to the weaker 2-edge-connected setting. The key step is showing that chains of pinched super-clean ladders must appear and adding them to the unavoidable collection, along with the expected consequences for minors, topological minors, and Eulerian subgraphs. They also note the extension works for multigraphs where needed. The argument supplies explicit constructions for the infinite case and stays self-contained without reducing to fitted parameters or hidden assumptions. The definitions of the new structures are given up front, which helps track how the drop in connectivity forces these extra unavoidable pieces. The central claim holds up on the evidence presented, with no visible internal gaps or unsupported reductions. One minor drawback is that the new ladder chains make the final list more technical than the 2-connected version, so readers need to absorb those definitions before the full statement is clear. That is typical for these structural extensions rather than a flaw. This is aimed at graph theorists working on unavoidable sets and connectivity levels between connected and 2-connected graphs. Specialists familiar with the prior 2-connected theorem will get the most direct value. I would send it for peer review; the extension is focused and the reasoning is grounded enough to merit referee time.

Referee Report

1 major / 3 minor

Summary. The paper extends the Allred-Ding-Oporowski theorem on unavoidable large induced subgraphs in large and infinite 2-connected graphs to the weaker setting of 2-edge-connected graphs. It establishes that chains of pinched super-clean ladders are ubiquitous in this class and incorporates them into an updated list of unavoidable induced subgraphs. The work derives consequences for large subgraphs, topological minors, minors, induced topological minors, induced minors, and Eulerian subgraphs, with explicit constructions for the infinite case and extensions to multigraphs.

Significance. If the central claims hold, this provides a natural and complete extension of the unavoidable-set theory from 2-connected to 2-edge-connected graphs, filling a gap between the connected and 2-connected cases. The introduction of chains of pinched super-clean ladders as the key new unavoidable structures, together with the self-contained proofs and explicit infinite-case constructions, strengthens the contribution. The derived consequences on minors and Eulerian subgraphs are of independent interest in structural graph theory.

major comments (1)

[§4] The adaptation of the Allred-Ding-Oporowski list relies on the claim that inserting the new ladder-chain structures requires no additional case distinctions that would invalidate the 2-edge-connected setting (§4 and the main theorem statement). A concrete verification that the new structures remain unavoidable even when bridges are forbidden only at the global level (but local 2-edge-connectivity may vary) would strengthen the argument.

minor comments (3)

[§3] The definitions of 'pinched super-clean ladder' and 'chain' in §3 would benefit from an explicit diagram or small example illustrating the pinching operation and how it preserves 2-edge-connectivity.
[Main theorem and §5] Notation for the unavoidable collection (e.g., the updated list including the new structures) should be introduced once and used consistently in the statement of the main theorem and in the corollaries on minors.
[Introduction] A brief comparison table or paragraph contrasting the 2-connected list with the new 2-edge-connected list would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation of minor revision. We address the single major comment below and will incorporate an explicit verification as suggested.

read point-by-point responses

Referee: [§4] The adaptation of the Allred-Ding-Oporowski list relies on the claim that inserting the new ladder-chain structures requires no additional case distinctions that would invalidate the 2-edge-connected setting (§4 and the main theorem statement). A concrete verification that the new structures remain unavoidable even when bridges are forbidden only at the global level (but local 2-edge-connectivity may vary) would strengthen the argument.

Authors: The main theorem and its proof in Section 4 are formulated directly for 2-edge-connected graphs, so the global prohibition on bridges is built into every step of the argument. The construction of chains of pinched super-clean ladders explicitly permits articulation points (hence varying local edge-connectivity) while preserving the global 2-edge-connectivity of the host graph; the reductions used to force these chains never assume uniform local connectivity. Consequently, no new case distinctions arise when moving from the 2-connected setting of Allred-Ding-Oporowski to the 2-edge-connected setting. To strengthen the exposition exactly as the referee suggests, we will insert a short clarifying paragraph (with a small illustrative example) immediately after the statement of the main theorem in §4. This paragraph will explicitly confirm that the unavoidability proof continues to hold under global 2-edge-connectivity alone. revision: yes

Circularity Check

0 steps flagged

Minor self-citation to prior 2-connected result; new structures proven independently

full rationale

The derivation introduces and proves ubiquity of chains of pinched super-clean ladders as new unavoidable structures specific to the 2-edge-connected setting, then inserts them into the list from the cited Allred-Ding-Oporowski theorem on 2-connected graphs. This extension step is self-contained with explicit constructions and does not reduce the central claim to a fitted parameter, self-definition, or load-bearing self-citation chain. The single overlapping-author citation supports the base case but is not the sole justification for the new ladder-chain results or the adaptation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper operates within standard graph theory and extends a cited prior theorem; no free parameters, new physical entities, or ad-hoc axioms beyond classical definitions of induced subgraphs and edge-connectivity are indicated.

axioms (1)

standard math Standard axioms of graph theory: definitions of induced subgraphs, 2-edge-connectivity, finite and infinite graphs, and multigraph extensions when appropriate.
Invoked throughout to support the structural claims.

pith-pipeline@v0.9.0 · 5715 in / 1191 out tokens · 46144 ms · 2026-05-22T22:29:07.601742+00:00 · methodology