PropositionStatement: 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.

Invariant of the recursive induced separator

PDF p. 3: Section 3, paragraph beginning Next and subsequent argument; PDF p. 4: Section 3, first two paragraphs

Statement

Let $k \geq 2$ be an integer, and let $H_{1}, H_{2}$ be non-isomorphic finite connected simple graphs, each with an edge, ordered so that $β (H_{1}) \geq β (H_{2})$ and, if equality holds, $∣ V (H_{1}) ∣ \geq ∣ V (H_{2}) ∣$ . For a graph with an edge, $β (H)$ is the greatest number of vertices in a block of $H$ ; for a nonempty edgeless graph, set $β (H) = 1$ . 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. Connected means that every two vertices are joined by a path.

Use the recursive induced-separator construction: an independent set $I$ of $H_{2}$ and its induced remainder $F = H_{2} - I$ satisfy $β (F) < β (H_{2})$ ; a finite simple core $A$ has no induced copy of $H_{1}$ and every colouring of its vertices with $k$ available colours has a monochromatic induced copy of $F$ . The construction sets $A_{1} = H_{2}$ and, for each integer $r$ with $2 \leq r \leq k$ , attaches disjoint copies of $A_{r - 1}$ to a copy of $A$ as specified there. Independent means that no edge has both endpoints in $I$ ; an induced copy is the image of an injective vertex map preserving adjacency and nonadjacency.

Then $A_{1} = H_{2}$ , and for every integer $r$ with $2 \leq r \leq k$ we have $A_{r} \in R_{i n d}^{r} (H_{2}) ∖ R_{i n d}^{r} (H_{1})$ . In fact the same membership and nonmembership hold for $r = 1$ . Here, for a positive integer $s$ , $R_{i n d}^{s} (H)$ is the class of nonempty finite simple graphs for which every map from the vertex set to ${1, \dots, s}$ has an induced copy of $H$ whose vertices all receive one colour; not every available colour need occur.

Statement references

Graph and colouring conventions

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

Recursive graphs Ar and their attachments

Induced vertex-Ramsey class

Unrestricted finite colourings and used palettes

Facts & Assumptions

[F1]

The construction gives $A_{1} = H_{2}$ and defines the finite graphs through stage $k$ under the stated hypotheses. Recursive graphs Ar and their attachments

[F2]

Under these hypotheses, $A_{1} \in R_{i n d}^{1} (H_{2})$ and $A_{1} \notin R_{i n d}^{1} (H_{1})$ . The implicit r=1 base case

[F3]

For each integer $r$ with $2 \leq r \leq k$ , if $A_{r - 1} \notin R_{i n d}^{r - 1} (H_{1})$ , then $A_{r} \notin R_{i n d}^{r} (H_{1})$ . Inductive colouring avoiding H1

[F4]

For each integer $r$ with $2 \leq r \leq k$ , if $A_{r - 1} \in R_{i n d}^{r - 1} (H_{2})$ , then $A_{r} \in R_{i n d}^{r} (H_{2})$ . Inductive Ramsey membership for H2

[F5]

A property of natural numbers holding at zero and passing from each number to its successor holds at every natural number. The principle of mathematical induction

Proof

Given: The graphs, ordering, choices and recursive construction in the statement.

Goal: Prove the asserted membership and nonmembership at every stage through $k$ , together with $A_{1} = H_{2}$ .

1.1F2givenbase

For a natural number $n$ , let $P (n)$ assert that, if $n + 1 \leq k$ , then $A_{n + 1} \in R_{i n d}^{n + 1} (H_{2})$ and $A_{n + 1} \notin R_{i n d}^{n + 1} (H_{1})$ . The base case $P (0)$ follows from F2.

2.1F3F4step 1.1ih

Suppose $P (n)$ . If $(n + 1) + 1 \leq k$ , then $n + 1 \leq k$ , so $P (n)$ supplies both properties at stage $n + 1$ . Since $2 \leq (n + 1) + 1 \leq k$ , F3 and F4 give the corresponding nonmembership and membership at stage $(n + 1) + 1$ . If $(n + 1) + 1 > k$ , the implication defining $P (n + 1)$ holds vacuously. Thus $P (n)$ implies $P (n + 1)$ in either case.

3.1F1F5step 2.1discharge-induction∎

Induction gives $P (n)$ for every natural number. For each integer $r$ with $1 \leq r \leq k$ , the number $n = r - 1$ is natural; taking this $n$ yields both properties at stage $r$ . In particular they hold throughout the requested range $2 \leq r \leq k$ , and F1 supplies $A_{1} = H_{2}$ . This proves the invariant.

Depends on

Used by · 1

Final induced-Ramsey 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, paragraph beginning Next and subsequent argument; PDF p. 4, Section 3, first two paragraphs