ExampleConstruction: AI-adaptedVerification: 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.

Final induced-Ramsey separator

PDF p. 4: Section 3, second paragraph

Example

Let $k$ be a natural number with $k \geq 2$ , 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}) ∣$ . A graph is connected if every two vertices are joined by a path. A block is a maximal 2-connected subgraph or a bridge with its endpoints; 2-connected means connected, having at least three vertices, and remaining connected after deletion of any vertex. A bridge is an edge whose deletion increases the number of connected components. 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$ .

Choose an independent set $I$ of $H_{2}$ and its nonempty induced remainder $F = H_{2} - I$ with $β (F) < β (H_{2})$ , and choose a finite simple core $A$ containing no induced copy of $H_{1}$ such that every colouring of its vertices with $k$ available colours has a monochromatic induced copy of $F$ . Independent means that no two vertices of $I$ are adjacent. An induced copy is the image of an injective vertex map preserving adjacency and nonadjacency. Construct $A_{1}, \dots, A_{k}$ by the specified recursive induced-separator construction, starting with $A_{1} = H_{2}$ and attaching copies of $A_{r - 1}$ to a copy of $A$ at stage $r$ .

Then $A_{k} \in R_{i n d}^{k} (H_{2}) ∖ R_{i n d}^{k} (H_{1})$ . Here $R_{i n d}^{k} (H)$ consists of the nonempty finite simple graphs whose every vertex map to ${1, \dots, k}$ has a monochromatic induced copy of $H$ ; colours need not all be used. Consequently the two induced vertex-Ramsey classes are distinct, contradicting any assumption that they are equal.

Example references

The natural numbers ℕ (von Neumann)

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Graph isomorphisms, automorphisms and graph complements

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]

Under the hypotheses and recursive construction in the example, for every $2 \leq r \leq k$ the invariant gives $A_{r} \in R_{i n d}^{r} (H_{2})$ and $A_{r} \notin R_{i n d}^{r} (H_{1})$ . Invariant of the recursive induced separator

[F2]

Membership in $R_{i n d}^{k} (H)$ means that every vertex colouring with the $k$ available colours has a monochromatic induced copy of $H$ ; a colouring need not use every colour. Induced vertex-Ramsey class Unrestricted finite colourings and used palettes

Verification

Given: The ordered graphs, choices of $I$ and $A$ , and recursive graphs in the example.

Goal: Verify the displayed class difference and the resulting inequality of classes.

1.1F1given

Since $k$ is a natural number with $k \geq 2$ , take $r = k$ in F1. Thus $A_{k} \in R_{i n d}^{k} (H_{2})$ and $A_{k} \notin R_{i n d}^{k} (H_{1})$ .

2.1F2step 1.1∎

By F2 these are membership and nonmembership in the stated classes, so $A_{k}$ lies in their displayed set difference. A graph belonging to one class and not the other witnesses that the classes are unequal; hence equality would be contradicted.

Depends on

Used by · 1

Induced part of Theorem 1.1

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. 4, Section 3, second paragraph