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 bounds in the edged-F case

PDF p. 3: Section 3, paragraph beginning First, edged-F case

Statement

Let $H_{1}, H_{2}$ be non-isomorphic finite connected simple graphs with edges, ordered so that $β (H_{1}) \geq β (H_{2})$ . Let $I$ be an independent set of $H_{2}$ such that $F = H_{2} - I$ satisfies $β (F) < β (H_{2})$ . An independent set contains no edge with both endpoints in it; $H_{2} - I$ is the induced graph on the vertices outside $I$ . Suppose that $F$ has an edge.

Then $β (F) \geq 2$ and $β (H_{1}) \geq 3$ . If $B$ is a block of $H_{1}$ of order $β (H_{1})$ , no copy of $F$ placed on a hyperedge in Construction 1 contains a subgraph isomorphic to $B$ .

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 deleting 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; for a nonempty edgeless graph it is $1$ . A copy of a graph is a subgraph isomorphic to it, allowing extra edges in the ambient graph.

Statement references

The independent set I and remainder F

Blocks and the parameter beta

Graph and colouring conventions

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

Facts & Assumptions

[F1]

The chosen independent remainder is a nonempty finite graph and satisfies $β (F) < β (H_{2}) \leq β (H_{1})$ . The independent set I and remainder F

[F2]

If an independent deletion from a finite simple graph with an edge leaves a graph with an edge, the remainder's largest nontrivial block order is at least two. Nonempty remainder after deleting an independent set

[F3]

A block of order at least three is 2-connected. Every 2-connected subgraph of a finite simple graph lies in a maximal 2-connected subgraph; consequently its order is at most the host's largest block order. Blocks and the parameter beta Block containment and monotonicity under subgraphs

[F4]

Each hyperedge piece in Construction 1 is isomorphic to $F$ . A copy is an isomorphic subgraph, and isomorphisms preserve and reflect adjacency. Construction 1: graph G(H,q,k) Graph and colouring conventions

Proof

Given: The stated graphs, independent set and remainder, with $F$ containing an edge.

Goal: Prove the two block-order bounds and the noncontainment assertion.

1.1F1F2given

By the independent-deletion bound, $β (F) \geq 2$ . The strict inequality $β (F) < β (H_{2})$ and the ordering $β (H_{2}) \leq β (H_{1})$ therefore give $β (H_{1}) \geq 3$ , since these block orders are integers.

2.1F1F3F4step 1.1∎

A largest block $B$ exists because $H_{1}$ has an edge. Its order is $β (H_{1}) \geq 3$ , so it is 2-connected. If a hyperedge piece contained a subgraph isomorphic to $B$ , transporting that subgraph across the piece's isomorphism with $F$ would give a 2-connected subgraph of $F$ of order $β (H_{1})$ . The containment bound would then give $β (H_{1}) \leq β (F)$ , contradicting $β (F) < β (H_{1})$ . Thus no such piece contains $B$ .

Depends on

Used by · 1

Block exclusion in the high-girth base graph

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