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.

Edgeless choice of A

PDF p. 3: Section 3, paragraph beginning First

Example

Let $H_{1}, H_{2}$ and the independent set $I$ be as in the induction setup: in particular, $H_{1}$ and $H_{2}$ are finite connected simple graphs, each with an edge, and $F = H_{2} - I$ is the induced graph on the vertices outside $I$ . Let $k \geq 1$ be an integer and suppose $F$ has no edges. Take $A$ to be an edgeless graph on $k (∣ F ∣ - 1) + 1$ vertices, where $∣ F ∣$ is the number of vertices of $F$ . Then $A \in Forb (H_{1}) \cap R_{i n d}^{k} (F)$ .

Here edgeless means having no edges. The class $Forb (H_{1})$ consists of graphs with no induced copy of $H_{1}$ ; $R_{i n d}^{k} (F)$ consists of graphs for which every assignment of the colours $1, \dots, k$ to vertices has a monochromatic induced copy of $F$ . An induced copy is the image of an injection preserving both adjacency and nonadjacency.

Example references

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

The independent set I and remainder F

Induced forbidden-subgraph class

Induced vertex-Ramsey class

Unrestricted finite colourings and used palettes

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

The cardinality | A| of a finite set

Facts & Assumptions

[F1]

Deleting an independent set from a finite simple graph with an edge leaves at least one vertex; in the induction setup this gives $∣ F ∣ \geq 1$ . Nonempty remainder after deleting an independent set The independent set I and remainder F

[F2]

If a finite set has more than $k (n - 1)$ elements, then every colouring of it with $k$ colours has a colour class with at least $n$ elements, for positive integers $k, n$ . Finite colour-class capacity and prescribed partitions

[F3]

An edgeless graph has empty edge set. An induced embedding is an injection preserving adjacency and nonadjacency, and finite sets of the same cardinality admit a bijection. A finite simple graph is a finite vertex set together with a set of two-element vertex subsets 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 The cardinality | A| of a finite set

[F4]

Membership in the forbidden class means absence of an induced copy; membership in the induced vertex-Ramsey class means that every permitted vertex colouring has a monochromatic induced copy. Induced forbidden-subgraph class Induced vertex-Ramsey class Unrestricted finite colourings and used palettes

Verification

Given: The graphs and integer $k$ in the example, with $F$ edgeless and $A$ edgeless on $k (∣ F ∣ - 1) + 1$ vertices.

Goal: Verify that $A$ belongs to both stated classes.

1.1givenF3F4

The graph $H_{1}$ has an edge, whereas $A$ has none. An induced embedding of $H_{1}$ into $A$ would send the endpoints of that edge to an edge of $A$ , which is impossible. Thus $A \in Forb (H_{1})$ .

1.2givenF1F2choose

Put $n = ∣ F ∣$ . By nonemptiness $n \geq 1$ , and $∣ V (A) ∣ = k (n - 1) + 1 > k (n - 1)$ . For any $k$ -colouring of $A$ , the capacity bound gives a colour class containing at least $n$ vertices. Choose $n$ of them.

2.1step 1.1step 1.2F3F4∎

Both $F$ and the graph induced by the chosen vertices are edgeless and have $n$ vertices. A bijection from $V (F)$ to those vertices therefore preserves adjacency and nonadjacency, giving a monochromatic induced copy of $F$ . Since the colouring was arbitrary, $A \in R_{i n d}^{k} (F)$ . Together with step 1.1 this proves the claimed intersection membership.

Depends on

Used by · 1

Existence of the base graph A

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, paragraph beginning First