Pith. sign in

REVIEW 3 major objections 4 minor 34 references

Infinite induced-saturated graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Nontrivial H gets an infinite graph that turns any local edit into H

desk verdict A complete countable characterization for induced-saturation, with a strong local-perturbation theorem; the only real soft spot is the two computer-assisted exhaustive checks that carry the load for small and borderline cases. read the letter →

arxiv 2506.08810 v3 pith:UZTN6BEY submitted 2025-06-10 math.CO

Marthe Bonamy , Carla Groenland , Tom Johnston , Natasha Morrison , Alex Scott This is my paper
classification math.CO MSC 05C6305C3505C75
keywords inducedsaturationinfinitegraphslocallyfiniteperturbationH-freefixingoperationsgatekeepersgraphcorescomputer-assistedproof
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

The paper proves a complete existence statement for infinite induced saturation. For every finite graph H that is neither a clique nor an independent set, there is a countably infinite graph G_H that contains no induced copy of H, yet any locally finite perturbation of G_H — finitely many edge additions or deletions incident to each vertex, with at least one change overall — contains an induced copy of H. This is far stronger than the usual one-edge notion of induced saturation, and it resolves the infinite analogue of a problem where the finite case already fails for H = P_4. The result is sharp: cliques and independent sets are exactly the excluded cases.

What carries the argument

The central mechanism is a fixing operation relative to a class of H-free graphs: given an H-free graph G and an unfixed pair xy, the operation glues a designed graph onto G so that the result stays in the class and any locally finite perturbation that touches xy forces an induced copy of H. The operation is driven by gatekeepers — an edge or non-edge uv of H whose removal leaves a glued copy that cannot create H — and by taking cores, iteratively peeling low-degree or twin vertices so that a construction for a smaller core extends to all graphs with that core. A scheduling lemma repeatedly applies these operations to a growing countable graph, ensuring every pair is eventually fixed while H never appears.

What would settle it

Run an independent exhaustive check: verify that every graph on 11 or fewer vertices (or its complement) falls into one of the listed cases, and independently search all bipartite graphs with |A|+|B|=12, |A| at least 5, |B| at least 3 for a 3-connected subgraph on at least 5 vertices. A single counterexample to either check would leave an exceptional H outside the proof of Theorem 1.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes Theorem 1: for every finite graph H that is not a clique or an independent set, there exists a countably infinite H-free graph G_H such that every locally finite perturbation of G_H contains an induced copy of H. The construction is not a single universal graph but a family of explicitly built graphs, each tailored to H through a sequence of fixing operations that take an unfixed pair of vertices and add a gadget — often an infinite blow-up — ensuring that any locally finite perturbation touching that pair creates a copy of H. The proof organizes all possible H into finitely many structural cases: 3-connected cores, K_{2,p} or K_{1,1,p} cores, forests with a unique maximum-degree vertex, and small exceptional graphs, with the small cases settled by an exhaustive computer-assisted check together with a scheduling lemma that upgrades fixing operations to the strong locally finite statement.

Load-bearing premise

The load-bearing assumption is that the exhaustive computer-assisted checks are error-free: the classification of every graph on at most 11 vertices (or its complement) into the proved cases, and the search showing every bipartite graph with |A|+|B|=12, |A| at least 5, |B| at least 3 contains a 3-connected subgraph on at least 5 vertices.

Editorial extensions

If this is right

  • For every finite H that is not a clique or independent set, a countably infinite H-induced-saturated graph exists (Corollary 2), including for graphs like P_4 where no finite example exists.
  • The space of countable H-free graphs, understood with locally finite edits as the notion of closeness, has points isolated in a very strong sense, so this space is very poorly connected.
  • The construction is complement-invariant: the complement of a strongly H-induced-saturated graph is strongly H-complement-induced-saturated.
  • The proof supplies explicit infinite graphs — the up-and-right graph, the torero graph, the rational geometric graph, and a blown-up lattice — that are strongly saturating for whole families of forbidden graphs at once.
  • The excluded classes are exactly cliques and independent sets, so the dichotomy is sharp and cannot be relaxed.

Reading between the lines

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

  • The fixing-operation and scheduling method suggests a general recipe: any hereditary graph class that stays closed under carefully chosen gluings can yield infinite graphs that are fragile under all locally finite edits, potentially transferring to tournaments, k-uniform hypergraphs, and edge-coloured complete graphs as the paper conjectures.
  • The up-and-right graph is strongly saturating precisely for graphs one edit away from a permutation graph, hinting at a broader principle: infinite strongly saturating graphs can be engineered from hereditary classes that are almost closed under single edge edits.
  • An independent brute-force verification of the small cases would make the theorem logically self-contained without relying on the correctness of the attached computer search, and would also pinpoint which exceptional graphs require the bespoke constructions of Sections 7.4 and 7.5.
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.

Referee Report

3 major / 4 minor

Summary. The paper proves Theorem 1: for every finite graph H that is neither a clique nor an independent set, there exists a countably infinite H-free graph G_H such that every locally finite perturbation of G_H contains an induced copy of H. This implies Corollary 2, the existence of countably infinite H-induced-saturated graphs for all such H. The proof introduces fixing operations relative to graph classes, gatekeepers, and several core notions (Section 4), and reduces the problem to four families of graphs via the structure theorem Theorem 10 for |V(H)| ≥ 12 (Section 5), with explicit constructions for forests with a unique maximum degree and for K2,p and K1,1,p 2-cores (Section 6). For |V(H)| ≤ 11, a computer-assisted classification identifies which of seven sufficient conditions hold for H or its complement, leaving eight exceptional graphs handled by ad hoc constructions (Section 7). A scheduling lemma (Lemma 17) converts fixing operations into strongly saturated graphs.

Significance. If the two computer-assisted steps are correct, Theorem 1 is a definitive and very strong answer to the existence question for infinite induced-saturated graphs: it isolates points in the space of H-free graphs under locally finite edit distance for every non-trivial H. The paper's structural toolkit (gatekeepers, cores, fixing operations) is elegant and reusable, and the explicit infinite graphs constructed (the up-and-right graph, the torero graph, the rational geometric graph) are interesting in their own right. The human-verifiable lemmas are written in detail. The main residual risk is that the two computer-assisted exhaustive checks—the bipartite claim inside the proof of Theorem 10 and the classification for graphs on at most 11 vertices in Section 7.3—are load-bearing and are not replaced by human-readable proofs; the second is backed by attached code, but the first is only asserted. If those checks are correct, the main result follows.

major comments (3)
  1. [Section 5, proof of Theorem 10] The sentence "This means that H contains a (not necessarily induced) bipartite subgraph H' = (A, B, E) with |A| + |B| = 12" is not justified as written, since A = V(H0) and B = V(H)\V(H0) have total size n ≥ 12, with equality only when n = 12. As written, the computer-search assertion that follows covers only the n = 12 case and Theorem 10 is not established for n > 12. Please supply the missing reduction: because |A| ≥ 5, |B| ≥ 3 and |A| + |B| ≥ 12, one can choose subsets A' ⊆ A and B' ⊆ B with |A'| + |B'| = 12, |A'| ≥ 5 and |B'| ≥ 3, and then delete edges inside the bipartite graph so that every b ∈ B' has exactly |A'| - 2 neighbours in A'; the search condition then applies to the resulting subgraph, and any 3-connected subgraph found there is also a subgraph of the original bipartite graph.
  2. [Section 5, proof of Theorem 10] The claim "A computer search shows that there is indeed a 3-connected subgraph on at least 5 vertices in every such bipartite graph" is load-bearing for Theorem 10 and hence for Theorem 1, yet it is stated with no description of the algorithm, no specification of the search space or the exact predicates checked, and no certificate or explicit pointer to code in this section. The text should either (a) give a complete, reproducible description of the finite check (code, canonical labelling method, and verifiable output), or (b) replace this step with a human-readable proof. As it stands, a reader cannot independently verify the key reduction for large graphs.
  3. [Section 7.3 and proof of Theorem 1] The exhaustive classification of graphs on at most 11 vertices is load-bearing for Theorem 1 in the small case, but the paper only sketches the gatekeeper check and refers to attached code. Please specify precisely which conditions are tested (the seven bullets in Section 7 plus their complements), how subgraph isomorphism with coloured vertices is decided, and how the completeness of the enumeration is guaranteed. In addition, the statement in the proof of Theorem 1 that "There are 8 graphs (E?qw, F?S|w, F?q|w and F?q w , and their complements)" uses names that are garbled in the text; a table with adjacency lists or readable names for these eight graphs would make the final cases checkable.
minor comments (4)
  1. [Section 2.4] The outline says "graphs H on at most 7 vertices in Section 7", but Section 7 actually handles graphs on at most 11 vertices; please correct the bound.
  2. [Section 5, proof of Lemma 12] The claims that H[A2 ∪ B1 ∪ B2] contains K4,2,2 and that H[A3 ∪ B1 ∪ B2 ∪ B3] contains K2,1,1,1 appear to hold in the complement of H rather than in H, since by construction there are no edges between A2 and B2 in H; if an overline was lost in the text, please correct the notation for these two subgraphs.
  3. [Section 7.4] The verification for the three graphs handled by the rational geometric graph is deferred to Figure 10 with the remark "we only sketch the constructions"; for a formal proof, a table of explicit rational coordinates for each of the three graphs would be preferable.
  4. [Section 7.1, proof of Theorem 19] The proof uses the phrase "the up and right graph is vertex transitive"; this is true for translations by rationals, but a one-sentence justification or a reference would help the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is self-contained and the only self-citation is motivational.

full rationale

No circularity found. The paper's target property, strong H-induced-saturation, is not assumed or fitted: fixing operations, gatekeepers, and cores are introduced as general definitions, and the paper proves their existence for each class of H via explicit gluing constructions and scheduling arguments (e.g., Lemmas 3, 7-9, 14-17) rather than importing the conclusion. The one self-citation, reference [3], is used only as motivational history for the P5 case and is not invoked in the proof of Theorem 1 or in any lemma; it is therefore not load-bearing. The computer-assisted checks in Section 7.3 and in the proof of Theorem 10 are finite exhaustive verifications that reduce the theorem to the proved cases; they involve no fitted parameters and the eight residual graphs are handled by separate explicit constructions (Sections 7.4-7.5), so any computational error would be a verifiability or correctness risk rather than a circularity. Theorem 19's characterization is proved from the definition of permutation graphs, and Lemma 17 is a genuine scheduling proof, not a definitional restatement of strong saturation. The derivation chain is therefore self-contained apart from external computational trust.

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

The paper is a purely mathematical proof. It introduces no fitted parameters and no new physical or structural entities beyond the standard vocabulary of graph theory. The central claim rests on the formal proof system of ordinary mathematics plus two computer-assisted checks.

assumptions (2)
  • standard math Standard ZFC set theory and the standard definitions of graphs, subgraphs, and induced subgraphs as presented in Section 3.
    The proof operates within ordinary mathematical foundations; no nonstandard axioms are introduced.
  • domain assumption The computer-assisted searches (for graphs up to 11 vertices and for the bipartite subgraph claim in Theorem 10) are correct and exhaustive.
    The classification of small graphs and one part of Theorem 10 rely on code attached to the arXiv submission; the paper does not provide a formal proof of these computational results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Infinite induced-saturated graphs." pith.science (2026). https://pith.science/paper/UZTN6BEY

@misc{pith2026250608810,
  author       = {Pith},
  title        = {Pith review of: Infinite induced-saturated graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UZTN6BEY}},
  note         = {Machine review of arXiv:2506.08810}
}
abstract

A graph $G$ is $H$-induced-saturated if $G$ is $H$-free but deleting any edge or adding any edge creates an induced copy of $H$. There are non-trivial graphs $H$, such as $P_4$, for which no finite $H$-induced-saturated graph $G$ exists. We show that for every finite graph $H$ that is not a clique or an independent set, there always exists a countable $H$-induced-saturated graph. In fact, we show that a far stronger property can be achieved: there is a countably infinite $H$-free graph $G$ such that any graph $G'\ne G$ obtained by making a locally finite set of changes to $G$ contains a copy of $H$.

Figures

Figures reproduced from arXiv: 2506.08810 by the authors.

Figure 1
Figure 1. The complement of the icosahedral graph is induced-saturated for [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. A sequence of graphs G1, G2, G3, . . . is obtained by repeatedly applying a fixing operation. The red edges and red non-edges are not fixed. We note that, for any i, and for any bad pair {x, y} of a graph Gi , there is a (later) index j such that perturbing {x, y} in Gj or any subsequent graph yields an induced P4. In other words, any bad pair is ultimately fixed. Therefore, there is a countably infinite P4-free gra… view at source ↗
Figure 3
Figure 3. The fixing operation for non-edges (left) and edges (right) is depicted. The blue [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: A “bad” 2-cut is shown. No such cuts are present in the [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: An example is given on how two graphs can be glued on non-edges [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: The bull graph. The torero graph has vertex set Q ∩ (0, 1) and there is an edge from x to y if and only if x + y > 1. Theorem 20. The torero graph is strongly H-induced-saturated whenever the (1, 1)-core of H is a copy of the bull graph or P4. Proof. We prove this theo…
Figure 7
Figure 7. Figure 7: We show in (a) how to create a bull when the edge [PITH_FULL_IMAGE:figures/full_fig_p021_7.png]
Figure 8
Figure 8. Figure 8: (a) The graph Dr[ with its only 2-cut highlighted in red. There are no 2-cuts which are edges, so every non-edge is a gatekeeper. (b) The graph with the edge xy removed, with x and y highlighted in red. (c) The two fragments of the graph created by taking the component…
Figure 9
Figure 9. Figure 9: The three problematic graphs which we handle using the rational geometric graph. [PITH_FULL_IMAGE:figures/full_fig_p022_9.png]
Figure 10
Figure 10. Figure 10: The left-hand side shows the constructions when removing an edge on the dotted [PITH_FULL_IMAGE:figures/full_fig_p023_10.png]
Figure 11
Figure 11. Figure 11: The final graph F?q˜w. We first give an auxiliary construction and then blow this up to allow for locally finite perturbations. Let G be the graph with vertex set Z 3 . We join the vertex (i, j, k) to (a, b, c) in G if they agree in at least one coordinate, i.e. i = a…
Figure 12
Figure 12. Figure 12: Examples of how to embed H into a copy of G when an edge of G has been per￾turbed. The dotted lines represent the location of the edge which was removed (top) or added (bottom). Suppose now that v ′ 1 v ′ 2 is perturbed in a locally finite perturbation of G′ where v ′…
Figure 13
Figure 13. Figure 13: The construction shows how to obtain a copy of [PITH_FULL_IMAGE:figures/full_fig_p024_13.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

34 extracted references · 33 canonical work pages

  1. [1]

    Axenovich and M

    M. Axenovich and M. Csik ´os. Induced saturation of graphs. Discrete Mathematics , 342(4):1195–1212, 2019

    work page 2019

  2. [2]

    Behrens, C

    S. Behrens, C. Erbes, M. Santana, D. Yager and E. Yeager. Graphs with induced saturation number zero. Electronic Journal of Combinatorics, 23(1):#P1.54, 2016

    work page 2016

  3. [3]

    Bonamy, C

    M. Bonamy, C. Groenland, T. Johnston, N. Morrison and A. Scott. Induced saturation for P5. https://tomjohnston.co.uk/blog/ 2020-05-22-induced-saturation-for-paths.html , 2020

    work page 2020

  4. [4]

    P. J. Cameron and J. Neˇsetˇril. Homomorphism-homogeneous relational structures. Com- binatorics, Probability and Computing, 15(1-2):91–103, 2006

    work page 2006

  5. [5]

    Cherlin and S

    G. Cherlin and S. Shelah. Universal graphs with a forbidden subtree. J. Comb. Theory Ser. B, 97(3):293–333, 2007

    work page 2007

  6. [6]

    Cherlin and S

    G. Cherlin and S. Shelah. Universal graphs with a forbidden subgraph: Block path solidity. Combinatorica, 36(3):249–264, 2016

    work page 2016

  7. [7]

    Cherlin and L

    G. Cherlin and L. Tallgren. Universal graphs with a forbidden near-path or 2-bouquet. Journal of Graph Theory, 56(1):41–63, 2007

    work page 2007

  8. [8]

    G. L. Cherlin. The Classification of Countable Homogeneous Directed Graphs and Countable Homogeneous n-tournaments, volume 621. American Mathematical Soc., 1998

    work page 1998

Show all 34 references
  1. [9]

    E.-K. Cho, I. Choi and B. Park. On induced saturation for paths. European Journal of Combinatorics, 91:103204, 2021

    2021

  2. [10]

    B. L. Currie, J. R. Faudree, R. J. Faudree and J. R. Schmitt. A survey of minimum saturated graphs. Electronic Journal of Combinatorics, DS19:36, 2021

    2021

  3. [11]

    R. Diestel. Graph Decompositions—A Study in Infinite Graph Theory . Oxford University Press, 1990

    1990

  4. [12]

    R. Diestel. Infinite Graphs, pages 209–281. Springer Berlin Heidelberg, Berlin, Heidelberg, 2017. 27

    2017

  5. [13]

    Diestel, R

    R. Diestel, R. Hahn and W. Vogler. Some remarks on universal graphs. Combinatorica, 5:283–293, 1985

    1985

  6. [14]

    Diestel and D

    R. Diestel and D. K ¨uhn. A universal planar graph under the minor relation. Journal of Graph Theory, 32(2):191–206, 1999

    1999

  7. [15]

    Dvo ˇr´ak

    V. Dvo ˇr´ak. Pn-induced-saturated graphs exist for all n ≥ 6. Electronic Journal of Combi- natorics, 27(4):#P4.43, 2020

    2020

  8. [16]

    Erd ˝os, A

    P. Erd ˝os, A. Hajnal and J. W. Moon. A problem in graph theory. American Mathematical Monthly, 71:1107–1110, 1964

    1964

  9. [17]

    X. Fan, S. Hajebi, S. Hajebi and S. Spirkl. Halfway to induced saturation for even cycles. arXiv preprint arXiv:2505.24100, 2025

    2025 arXiv

  10. [18]

    F ¨uredi and P

    Z. F ¨uredi and P. Komj´ath. Nonexistence of universal graphs without some trees. Combi- natorica, 17(2), 1997

    1997

  11. [19]

    F ¨uredi and P

    Z. F ¨uredi and P. Komj ´ath. On the existence of countable universal graphs. Journal of Graph Theory, 25(1):53–58, 1997

    1997

  12. [20]

    M. Hamann. Connected-homogeneous digraphs. Habilitationsschrift, University of Ham- burg, 2014

    2014

  13. [21]

    M. Hamann. The classification of finite and locally finite connected-homogeneous di- graphs. Combinatorica, 37:183–222, 2017

    2017

  14. [22]

    C. W. Henson. A family of countable homogeneous graphs. Pacific J. Math., 38(1):69–83, 1971

    1971

  15. [23]

    Komj ´ath, A

    P. Komj ´ath, A. H. Mekler and J. Pach. Some universal graphs. Israel Journal of Mathe- matics, 64(2):158–168, 1988

    1988

  16. [24]

    Komj ´ath

    P. Komj ´ath. The chromatic number of infinite graphs—a survey. Discrete Mathematics, 311(15):1448–1450, 2011

    2011

  17. [25]

    Komj ´ath and J

    P. Komj ´ath and J. Pach. Universal graphs without large bipartite subgraphs.Mathematika, 31(2):282–290, 1984

    1984

  18. [26]

    A. H. Lachlan and R. E. Woodrow. Countable ultrahomogeneous undirected graphs. Transactions of the American Mathematical Society, 262(1):51–94, 1980

    1980

  19. [27]

    R. R. Martin and J. J. Smith. Induced saturation number. Discrete Mathematics , 312(21):3096–3106, 2012

    2012

  20. [28]

    J. Pach. A problem of Ulam on planar graphs. European Journal of Combinatorics , 2(4):357–361, 1981

    1981

  21. [29]

    R. Rado. Universal graphs and universal functions. Acta Arithmetica, 9:331–340, 1964

    1964

  22. [30]

    E. R ¨aty. Induced saturation of P6. Discrete Mathematics, 343(1):111641, 2020

    2020

  23. [31]

    J. H. Schmerl. Countable homogeneous partially ordered sets. Algebra universalis , 9(1):317–321, 1979. 28

    1979

  24. [32]

    M. Stein. Extremal infinite graph theory. Discrete Mathematics, 311(15):1472–1496, 2011

    2011

  25. [33]

    C. M. Tennenhouse. Induced subgraph saturated graphs. Theory and Applications of Graphs, 3(2), 2016

    2016

  26. [34]

    Thomassen

    C. Thomassen. Duality of infinite graphs. Journal of Combinatorial Theory, Series B , 33(2):137–160, 1982. 29

    1982

Pith tools

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