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.

Single-vertex target case

PDF p. 3: Section 3, first paragraph after Figure 1

Example

Let $k$ be a positive integer, and let $H_{1}, H_{2}$ be non-isomorphic finite simple connected graphs with at least one vertex each. If $H_{1} = K_{1}$ , then $K_{1} \in R_{i n d}^{k} (H_{1}) ∖ R_{i n d}^{k} (H_{2})$ . The same conclusion with the target labels exchanged holds when $H_{2} = K_{1}$ . Consequently, after these cases are handled, both connected targets have at least one edge.

Here $K_{1}$ is the complete graph on one vertex. A graph is connected if every two of its vertices are joined by a path, a finite list of distinct vertices with consecutive vertices adjacent. The induced $k$ -colour vertex-Ramsey class of a target consists of the graphs in which every vertex colouring by $k$ available colours has a monochromatic induced copy of that target. An induced copy is the image of an injection preserving both adjacency and nonadjacency; monochromatic means that all its vertices have the same colour.

Example references

Graph and colouring conventions

Induced vertex-Ramsey class

Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices

Induced embeddings and induced copies of a graph

Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set

Facts & Assumptions

[F1]

By Graph and colouring conventions and Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices, a finite simple graph has edges consisting of pairs of distinct vertices, and $K_{1}$ has one vertex and no edges.

[F2]

By Induced vertex-Ramsey class and Induced embeddings and induced copies of a graph, class membership requires a monochromatic induced embedding for every $k$ -colouring; such an embedding is injective and preserves and reflects adjacency.

[F3]

By Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set, any two vertices of a connected graph are joined by a path whose consecutive vertices are adjacent.

Verification

Given: The hypotheses of the example, first with $H_{1} = K_{1}$ .

Goal: Establish the displayed class difference and the stated reduction.

1.1givenF1F2

For any $k$ -colouring of $K_{1}$ , its only vertex is monochromatic, and the identity map is an induced embedding of $H_{1} = K_{1}$ into $K_{1}$ . Hence $K_{1} \in R_{i n d}^{k} (H_{1})$ .

2.1givenF1F2step 1.1

The nonempty graph $H_{2}$ cannot have exactly one vertex: a finite simple graph on one vertex has no edges and is isomorphic to $K_{1}$ . Thus it has at least two vertices, so no injection from its vertex set to the one-vertex set of $K_{1}$ exists. In particular, $K_{1}$ contains no induced copy of $H_{2}$ under any colouring; since $k \geq 1$ , a $k$ -colouring of $K_{1}$ exists, and $K_{1} \notin R_{i n d}^{k} (H_{2})$ . Exchanging the labels proves the symmetric case.

3.1givenF1F3step 2.1∎

If a nonempty connected simple graph has at least two vertices, a path between two distinct vertices has a consecutive pair, which is an edge. Every nonempty one-vertex simple graph is isomorphic to $K_{1}$ ; hence, once the single-vertex cases have been handled, each connected target has an edge.

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. 3, Section 3, first paragraph after Figure 1