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

Ordinary part of Theorem 1.1

PDF p. 1: Theorem 1.1, first inequality; PDF p. 2: Section 3, ordinary-class argument

Statement

Let $H_{1}, H_{2}$ be non-isomorphic finite simple graphs, each with at least one vertex, and let $k$ be a positive integer. Then $R^{k} (H_{1}) \neq R^{k} (H_{2})$ .

Graphs are isomorphic when a bijection of their vertex sets preserves and reflects adjacency. The ordinary vertex-Ramsey class $R^{k} (H)$ consists of the nonempty finite simple graphs $G$ such that every function $V (G) \to {1, \dots, k}$ has a monochromatic ordinary copy of $H$ . An ordinary copy is a subgraph isomorphic to $H$ ; extra host edges between its vertices are allowed.

Statement references

Graph and colouring conventions

Graph isomorphisms, automorphisms and graph complements

Ordinary vertex-Ramsey class

Facts & Assumptions

[F1]

For non-isomorphic nonempty finite simple graphs, the ordinary one-colour vertex-Ramsey classes are distinct (The k=1 case).

[F2]

If nonempty finite simple graphs $A, B$ have $∣ A ∣ < ∣ B ∣$ and $k \geq 2$ , there is a graph in $R^{k} (A) ∖ R^{k} (B)$ (Complete-graph separator when orders differ). Here graph order $∣ A ∣$ is the number of vertices of $A$ (Order, size, complement and independence number).

[F3]

If non-isomorphic nonempty finite simple graphs have equal order and $k \geq 2$ , they can be labelled so that there is a graph in the ordinary $k$ -colour class of the second but not the first (Join separator for equal-order targets).

Proof

Given: Non-isomorphic finite simple graphs $H_{1}, H_{2}$ , each with at least one vertex, and a positive integer $k$ .

Goal: Show that their ordinary $k$ -colour vertex-Ramsey classes are distinct.

1.1givenF1

If $k = 1$ , the one-colour distinction fact gives $R^{1} (H_{1}) \neq R^{1} (H_{2})$ .

1.2givenF2choose

Suppose $k \geq 2$ and the graph orders differ. Label the graph of smaller order $A$ and the other $B$ . The different-order separator gives a graph belonging to $R^{k} (A)$ but not $R^{k} (B)$ , so the two classes differ.

2.1givenF3step 1.1step 1.2∎

Suppose $k \geq 2$ and the graph orders are equal. The equal-order separator gives, after possibly exchanging the labels, a graph belonging to one of the two classes and not the other. Thus the classes differ in this case as well. The cases in steps 1.1, 1.2 and 2.1 exhaust positive $k$ and the possible orders, proving the theorem.

Depends on

Used by · 1

Theorem 1.1: both vertex-Ramsey distinctions

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. 1, Theorem 1.1, first inequality; PDF p. 2, Section 3, ordinary-class argument