LemmaStatement: AI-adaptedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Block exclusion in the high-girth base graph

PDF p. 3: Section 3, paragraph beginning First, choice of B and A

Statement

Let $H_{1}, H_{2}$ be non-isomorphic finite connected simple graphs with edges, with $β (H_{1}) \geq β (H_{2})$ . Let $I$ be an independent set of $H_{2}$ for which $F = H_{2} - I$ has an edge and $β (F) < β (H_{2})$ . Here an independent set has no edge between two of its vertices, and $H_{2} - I$ is the graph induced on the remaining vertices.

A block is a maximal 2-connected subgraph or a bridge together with its endpoints. A graph is 2-connected if it has at least three vertices, is connected, and remains connected after deletion of any one vertex; a bridge is an edge whose deletion increases the number of connected components. For a nonempty graph with an edge, $β$ is the largest number of vertices in a block, and for a nonempty edgeless graph it is $1$ . Choose a block $B$ of $H_{1}$ of order $β (H_{1})$ , put $q = ∣ E (B) ∣ + 2$ , and let $A = G (F, q, k)$ be any graph obtained by Construction 1 for a positive integer $k$ .

Then $A$ contains no ordinary copy of $B$ . Consequently $A \in Forb (B)$ and $A \in Forb (H_{1})$ , where $Forb (J)$ is the class of finite nonempty simple graphs with no induced copy of $J$ .

Statement references

Graph and colouring conventions

Blocks and the parameter beta

Block bounds in the edged-F case

Construction 1: graph G(H,q,k)

Induced forbidden-subgraph class

Ordinary embeddings as injections preserving edges

Induced embeddings and induced copies of a graph

Facts & Assumptions

[F1]

Under the stated hypotheses, $β (H_{1}) \geq 3$ , and no piece of Construction 1 obtained from $F$ contains an ordinary copy of $B$ . A block of order at least three is 2-connected. Block bounds in the edged-F case Blocks and the parameter beta

[F2]

Construction 1 uses a finite hypergraph $H = (V, E)$ of Berge girth at least $q$ and pieces $J_{e} = (e, E_{e})$ isomorphic to $F$ . Its graph is $A = (V, ⋃_{e \in E} E_{e})$ , so it is the hyperedge-indexed graph realisation of these pieces. A Berge cycle of length $s \geq 2$ consists of distinct hyperedges $e_{0}, \dots, e_{s - 1}$ and distinct vertices $x_{0}, \dots, x_{s - 1}$ with $x_{i} \in e_{i} \cap e_{i + 1}$ , indices taken modulo $s$ . Berge girth is the least length of such a cycle, or $\infty$ if none exists. Construction 1: graph G(H,q,k) Graph realisations with possibly different hyperedge pieces Berge cycles, incidence graphs and girth

[F3]

In a graph realisation over a finite hypergraph of Berge girth at least $q \geq 3$ , every ordinary occurrence of a 2-connected graph with fewer than $q$ edges lies in one hyperedge piece, with both its vertices and its edges contained in that piece. The realisation and girth conventions are those in F2. Small 2-connected subgraphs localise in high-girth pieces Graph realisations with possibly different hyperedge pieces Berge cycles, incidence graphs and girth

[F4]

An ordinary copy is a subgraph isomorphic to the copied graph. An induced copy is an ordinary copy that contains every host edge between its vertices. A graph belongs to $Forb (J)$ precisely when it has no induced copy of $J$ . Graph and colouring conventions Ordinary embeddings as injections preserving edges Induced embeddings and induced copies of a graph Induced forbidden-subgraph class

Proof

Given: The graphs, independent set, block, positive integer $k$ and construction choices in the statement.

Goal: Exclude ordinary copies of $B$ from $A$ and deduce both forbidden-class memberships.

1.1givenF1F2F3

The block bounds give $∣ V (B) ∣ = β (H_{1}) \geq 3$ , so $B$ is 2-connected, and every piece of the construction excludes an ordinary copy of $B$ . By F2, $A$ is the realisation of the specified pieces over a finite hypergraph with the stated Berge girth. Since $∣ E (B) ∣ < ∣ E (B) ∣ + 2 = q$ and $q \geq 3$ , all hypotheses of F3 hold for $B$ in $A$ . An ordinary occurrence in $A$ would lie in a single piece, contrary to its exclusion there. Thus $A$ has no ordinary copy of $B$ .

2.1givenF4step 1.1∎

Every induced copy of $B$ is an ordinary copy, so $A \in Forb (B)$ . If $A$ contained an induced copy of $H_{1}$ , the image of the subgraph $B \subseteq H_{1}$ under the isomorphism onto that induced copy would be an ordinary copy of $B$ in $A$ . This contradicts step 1.1. Hence $A \in Forb (H_{1})$ .

Depends on

Used by · 1

Existence of the base graph A

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.

Sources

Maria Axenovich and Patrick Schmitteckert, Non-isomorphic graphs have distinct vertex-Ramsey classes, arXiv:2610.03704v1 · PDF p. 3, Section 3, paragraph beginning First, choice of B and A