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.

Induced part of Theorem 1.1

PDF p. 1: Theorem 1.1, second inequality; PDF p. 2: Section 3, induced-class reduction; PDF p. 3: Section 3, recursive construction; PDF p. 4: Section 3, conclusion

Statement

For any two non-isomorphic finite simple graphs $H_{1}, H_{2}$ with at least one vertex each and any positive integer $k$ , $R_{i n d}^{k} (H_{1}) \neq R_{i n d}^{k} (H_{2})$ .

An isomorphism is a vertex bijection preserving and reflecting adjacency. The induced $k$ -colour vertex-Ramsey class $R_{i n d}^{k} (H)$ consists of the nonempty finite simple graphs $G$ such that every map $V (G) \to {1, \dots, k}$ has a monochromatic induced copy of $H$ . Such a copy is the image of an injective vertex map preserving and reflecting adjacency, with all image vertices assigned the same colour. Equality of classes means equality of membership for every such $G$ .

Statement references

Graph and colouring conventions

Induced vertex-Ramsey class

Graph isomorphisms, automorphisms and graph complements

Induced embeddings and induced copies of a graph

Facts & Assumptions

[F1]

Non-isomorphic nonempty finite simple graphs have distinct induced one-colour vertex-Ramsey classes. The k=1 case

[F2]

For $k \geq 2$ , an equal-class pair of non-isomorphic nonempty finite simple graphs can be replaced, if necessary by taking both complements, by an equal-class pair of non-isomorphic connected graphs. A graph is connected if every two vertices are joined by a path. Reduction to connected targets

[F3]

If one of two non-isomorphic connected nonempty finite simple targets is the one-vertex complete graph $K_{1}$ , then $K_{1}$ belongs to its induced class and not to the other's. Every connected nonempty simple graph not isomorphic to $K_{1}$ has an edge. Single-vertex target case

[F4]

For connected non-isomorphic finite simple graphs with edges, label the targets so that $β (H_{1}) \geq β (H_{2})$ and, in case of equality, $∣ V (H_{1}) ∣ \geq ∣ V (H_{2}) ∣$ . Here 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 one vertex. A bridge is an edge whose deletion increases the number of connected components. For a graph with an edge, $β$ is the largest block order; for a nonempty edgeless graph it is $1$ . With this labelling $H_{2}$ contains no induced copy of $H_{1}$ . Blocks and the parameter beta Ordering targets and excluding H1 from H2

[F5]

For connected $H_{2}$ with an edge, there is an independent set $I$ such that $F = H_{2} - I$ is nonempty and $β (F) < β (H_{2})$ . Independent means that no two vertices in $I$ are adjacent; $H_{2} - I$ is the induced graph on the remaining vertices. For the ordered targets and any positive $k$ , there is a finite simple graph $A$ containing no induced copy of $H_{1}$ such that every $k$ -colouring of $A$ has a monochromatic induced copy of $F$ . Independent deletion decreases beta The independent set I and remainder F Existence of the base graph A

[F6]

Given the ordered connected targets with edges, such an independent set $I$ , remainder $F$ and base graph $A$ , the recursive induced-separator construction starts with $A_{1} = H_{2}$ and attaches copies of the preceding graph to a copy of $A$ at each subsequent stage. For $k \geq 2$ , its final graph $A_{k}$ belongs to $R_{i n d}^{k} (H_{2})$ and not to $R_{i n d}^{k} (H_{1})$ . Recursive graphs Ar and their attachments Final induced-Ramsey separator

Proof

Given: Non-isomorphic nonempty finite simple graphs $H_{1}, H_{2}$ and a positive integer $k$ .

Goal: Show that their induced $k$ -colour vertex-Ramsey classes differ.

1.1givenF1F2assume-contra

If $k = 1$ , the conclusion follows from F1. Suppose henceforth that $k \geq 2$ and, for a contradiction, that the two classes are equal. By F2, replace the targets if necessary by their complements and retain the names $H_{1}, H_{2}$ ; the resulting targets are connected, non-isomorphic and still have equal induced classes.

2.1givenF3step 1.1

If either target is isomorphic to $K_{1}$ , it has exactly one vertex and is a copy of $K_{1}$ . Composing an induced embedding with this isomorphism shows that its induced Ramsey class is the same as that of $K_{1}$ . F3 then gives a graph belonging to exactly one of the two classes, contradicting equality. Hence neither target is isomorphic to $K_{1}$ , and F3 says that each has an edge.

3.1F4F5step 1.1step 2.1choose

Relabel the targets in the order specified in F4. By F5 choose an independent set $I$ of $H_{2}$ whose nonempty remainder $F = H_{2} - I$ satisfies $β (F) < β (H_{2})$ . The base-graph existence result in F5 then supplies a graph $A$ with no induced $H_{1}$ and with a monochromatic induced $F$ in every $k$ -colouring. These choices satisfy the hypotheses of F6.

4.1F6step 1.1step 3.1discharge-contradiction∎

Construct $A_{k}$ as in F6. It is in the induced $k$ -colour Ramsey class of $H_{2}$ and outside that of $H_{1}$ , contradicting equality of the classes. Thus the classes differ for $k \geq 2$ as well. Together with the one-colour case, this proves the statement.

Source notes

The article citation attributes the theorem. The proof above applies the stated local reduction and separator results, including the separate existence of the independent deletion and base graph.

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, second inequality; PDF pp. 2–4, Section 3