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.

The implicit $r = 1$ base case

PDF p. 3: Section 3, target ordering and definition A1 := H2

Statement

Let $H_{1}, H_{2}$ be non-isomorphic connected finite simple graphs, each containing an edge. Order them so that $β (H_{1}) \geq β (H_{2})$ and, if equality holds, $∣ V (H_{1}) ∣ \geq ∣ V (H_{2}) ∣$ . Set $A_{1} = H_{2}$ . Then $A_{1} \in R_{i n d}^{1} (H_{2})$ and $A_{1} \notin R_{i n d}^{1} (H_{1})$ .

Here $β (H)$ is the greatest number of vertices in a block of $H$ ; a block is a maximal 2-connected subgraph or a bridge with its endpoints. A graph is 2-connected if it has at least three vertices, is connected, and remains connected after deletion of any vertex; a bridge is an edge whose deletion increases the number of connected components. A graph is connected if every two vertices are joined by a path. An induced copy of $H$ in $G$ is a subgraph isomorphic to $H$ that contains every edge of $G$ between its vertices. The class $R_{i n d}^{1} (H)$ consists of nonempty finite simple graphs in which every vertex colouring with the single available colour has a monochromatic induced copy of $H$ .

Statement references

Graph and colouring conventions

Induced vertex-Ramsey class

Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges

Ordering targets and excluding H1 from H2

Facts & Assumptions

[F1]

Under the stated hypotheses and ordering, $H_{2} \in Forb (H_{1})$ , meaning that $H_{2}$ contains no induced copy of $H_{1}$ (Ordering targets and excluding H1 from H2, Induced forbidden-subgraph class).

[F2]

Each of the non-isomorphic nonempty finite simple graphs $H_{1}, H_{2}$ belongs to its own induced one-colour vertex-Ramsey class (The k=1 case).

[F3]

Membership in $R_{i n d}^{1} (H)$ requires an induced copy of $H$ that is monochromatic for every colouring under consideration; in particular, if the host has no induced copy of $H$ , the constant one-colour map witnesses nonmembership (Induced vertex-Ramsey class, Graph and colouring conventions).

Proof

Given: The graphs and ordering in the statement, with $A_{1} = H_{2}$ .

Goal: Establish the two asserted induced one-colour class memberships.

1.1givenF2

The self-membership assertion applied to $H_{2}$ gives $H_{2} \in R_{i n d}^{1} (H_{2})$ . Since $A_{1} = H_{2}$ , this is the first assertion.

2.1givenF1F3∎

The ordering lemma gives that $H_{2}$ has no induced copy of $H_{1}$ . The constant map $V (H_{2}) \to {1}$ is a one-colouring and has no monochromatic induced copy of $H_{1}$ , because there is no induced copy at all. Thus $H_{2} \notin R_{i n d}^{1} (H_{1})$ , and $A_{1} = H_{2}$ gives the second assertion.

Depends on

Used by · 1

Invariant of the recursive induced separator

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, target ordering and definition A1 := H2

The implicit r=1r=1 base case