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.

Reduction to connected targets

PDF p. 2: Section 3, final paragraph; PDF p. 3: Section 3, paragraph immediately after Figure 1

Statement

Let $k \geq 2$ be an integer and let $H_{1}, H_{2}$ be non-isomorphic finite simple graphs with nonempty vertex sets. If $R_{i n d}^{k} (H_{1}) = R_{i n d}^{k} (H_{2})$ , then $H_{1}$ and $H_{2}$ are either both connected or both disconnected. In the latter case their complements are connected, non-isomorphic, and have equal induced $k$ -colour vertex-Ramsey classes. Thus an equal-class pair of non-isomorphic targets can be replaced, if necessary, by such a pair of connected targets.

Here connected means that every two vertices are joined by a path. An isomorphism is a bijection preserving and reflecting adjacency. The complement $\overline{H}$ has the same vertices as $H$ and has an edge between two distinct vertices exactly when $H$ does not. The class $R_{i n d}^{k} (H)$ consists of the nonempty finite simple graphs $G$ for which every function $V (G) \to {1, \dots, k}$ has a monochromatic induced copy of $H$ : an injective image preserving and reflecting adjacency on which the function is constant. Equality means equality of membership for every such $G$ .

Statement references

Graph and colouring conventions

Induced vertex-Ramsey class

Order, size, complement and independence number

Connected graphs and connected components defined by the existence of vertex paths

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

Graph isomorphisms, automorphisms and graph complements

Facts & Assumptions

Given: An integer $k \geq 2$ and non-isomorphic nonempty finite simple graphs $H_{1}, H_{2}$ with equal induced $k$ -colour vertex-Ramsey classes.

Goal: Prove the common connectivity status and the stated reduction by complementation.

[F1]

A nonempty finite simple graph $H$ has the Ramsey repetition property at positive $k$ exactly when it is connected. The property says that for every nonempty finite simple graph $A$ and positive integer $q$ , $A$ belongs to $R_{i n d}^{k} (H)$ exactly when $q A$ does. Here $q A$ is the disjoint union of $q$ copies of $A$ . Lemma 2.1: repetition characterizes connectivity Ramsey repetition property at fixed k The disjoint multiple qA

[F2]

For nonempty finite simple targets and positive $k$ , their induced $k$ -colour vertex-Ramsey classes are distinct exactly when the corresponding classes of their complements are distinct. Complementation preserves distinction of induced classes

[F3]

The connected components of a nonempty finite graph partition its vertices. A disconnected graph therefore has at least two connected components, and the complement of a finite simple graph with at least two connected components is connected. Connected graphs and connected components defined by the existence of vertex paths The connected components of a graph partition its vertex set and are its maximal connected subgraphs Complement of a disconnected graph is connected

[F4]

Complementation keeps the vertex set and reverses adjacency for distinct vertices; complementing twice returns the original finite simple graph. An isomorphism preserves and reflects adjacency. Graph isomorphisms, automorphisms and graph complements Complementation transports induced copies on fixed vertices

Proof

technique · direct

1.1givenF1

Equality of the two class membership predicates applies both to $A$ and to $q A$ , for every nonempty finite simple graph $A$ and positive integer $q$ . Consequently the equivalence defining the repetition property holds for $H_{1}$ exactly when it holds for $H_{2}$ . By F1, $H_{1}$ is connected exactly when $H_{2}$ is connected.

2.1givenF2F3step 1.1

Suppose both targets are disconnected. By F3, each has at least two connected components, so both complements are connected. The complements have equal induced classes: otherwise F2 would imply that the original classes are distinct, contrary to the hypothesis.

3.1givenF4step 1.1step 2.1∎

If an isomorphism existed between the complements, then, because it preserves and reflects adjacency and complementation reverses adjacency on distinct pairs, the same bijection would be an isomorphism between the twice-complemented graphs $H_{1}$ and $H_{2}$ . This contradicts their non-isomorphism. Thus the complements are non-isomorphic. If the original targets are connected, retain them; otherwise step 2.1 and this step give the required connected pair.

Source notes

The cited article passage attributes the reduction. The argument here spells out the repetition-property comparison and the preservation of non-isomorphism under complementation.

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. 2, Section 3, final paragraph; PDF p. 3, Section 3, paragraph immediately after Figure 1