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.

Completion inside the join separator

PDF p. 2: Section 3, ordinary classes, red n-vertex set

Statement

Let $H_{2}$ be a finite simple graph of order $n \geq 1$ , and let $k \geq 2$ be an integer. Form $G = H_{2} \lor K_{(k - 1) (n - 1)}$ from disjoint copies. Every $k$ -colouring of $V (G)$ has at least $n$ vertices of one colour. Any set $S$ of $n$ vertices of that colour induces a graph $G [S] = G^{'} \lor K_{n - ℓ}$ , up to the canonical identification of its parts, where $G^{'}$ is the graph induced by the $ℓ$ selected vertices in the $H_{2}$ part and $0 \leq ℓ \leq n$ . This induced graph contains an ordinary copy of $H_{2}$ , and that copy is monochromatic.

Here the order of a graph is the number of its vertices. A finite simple graph has a finite vertex set and edges that are two-element subsets of it. A $k$ -colouring assigns each vertex one of $k$ colours, without requiring all colours to be used. An induced graph on a vertex set retains exactly the host edges with both endpoints in that set. The join retains the edges in its disjoint parts and adds all cross-edges; $K_{m}$ is the complete graph on $m$ vertices, with every two distinct vertices adjacent. For $m = 0$ , $K_{0}$ is the empty graph, and a join with an empty part has the edges of its other part. An ordinary copy is a subgraph isomorphic to the target, so extra host edges between its vertices are allowed.

Facts & Assumptions

Given: $H_{2}$ , $n$ , $k$ , and $G$ as in the statement, together with a $k$ -colouring of $V (G)$ .

Goal: Find $n$ vertices of one colour and prove the stated induced-join and ordinary-copy assertions for every such set.

[F1]

The join has disjoint parts inducing the given graphs and all possible cross-edges. Its construction permits an empty part. Induced subgraphs retain exactly the edges whose endpoints are selected. See Join of graphs and Subgraphs, induced subgraphs and spanning subgraphs.

[F2]

Graph order is vertex-set cardinality; disjoint finite sets have union cardinality equal to the sum of their cardinalities. A subset of a finite set is finite and has cardinality at most that of the ambient set. See Order, size, complement and independence number, The cardinality | A| of a finite set, The sum rule: a finite disjoint union is finite with | A ∪ B| = | A| + | B| and |⋃_i ∈ I Aᵢ| = ∑_i ∈ I| Aᵢ|, and a sum over a finite index set splits along a partition, and A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A.

[F3]

A $k$ -colouring is a function into ${1, \dots, k}$ , and a set is monochromatic when all its vertices receive the same value. If a finite set has more than $k (n - 1)$ elements, every such colouring has a colour class of at least $n$ elements. See Unrestricted finite colourings and used palettes and Finite colour-class capacity and prescribed partitions.

[F4]

If $J$ has $n$ vertices, $W \subseteq V (J)$ has $ℓ$ vertices, and $C$ is a disjoint set of $n - ℓ$ vertices, the complete connection of $J [W]$ and the complete graph on $C$ contains an ordinary copy of $J$ . This includes $ℓ = 0$ and $ℓ = n$ . An ordinary embedding gives a copy using its image edges. See Completing a restricted target with universal clique vertices and Ordinary embeddings as injections preserving edges.

[F5]

For natural numbers $ℓ \leq n$ , write $n - ℓ$ for the unique natural number $q$ with $ℓ + q = n$ . Existence follows from the additive definition of natural order. Addition is commutative, and $a + r = b + r$ implies $a = b$ ; hence $ℓ + q = ℓ + q^{'}$ implies $q = q^{'}$ . See Order on the natural numbers, Addition is commutative, and Addition is cancellative.

Proof

Given: The graph and colouring in the statement. Goal: Establish the colour-class, induced-join, and monochromatic-copy claims.

1.1givenF1F2F3

Let $A$ and $B$ be the vertex sets of the actual $H_{2}$ and clique parts of $G$ , respectively, and put $J = G [A]$ . The join provides a canonical bijection $ι : V (H_{2}) \to A$ preserving and reflecting edges, so $J$ is a copy of $H_{2}$ . Thus $∣ A ∣ = n$ and $∣ B ∣ = (k - 1) (n - 1)$ . Their disjoint union has $n + (k - 1) (n - 1) = k (n - 1) + 1$ vertices. By colour-class capacity, some colour class has at least $n$ vertices; choose any $n$ of them and call the resulting set $S$ .

2.1step 1.1F1F2F5

Put $W = S \cap A$ , $C = S \cap B$ , and $ℓ = ∣ W ∣$ . These are subsets of the actual vertex sets of the join: $W \subseteq V (J) = A$ and $C \subseteq B$ , so $W \cap C = \emptyset$ and $W \cup C = S$ . The subset bound and sum rule give $0 \leq ℓ \leq n$ and $ℓ + ∣ C ∣ = n$ . The unique-gap characterization in F5 therefore gives $∣ C ∣ = n - ℓ$ . The edges induced on $W$ are exactly those of $J [W]$ , those on $C$ form a complete graph, and all cross-edges are present. Thus $G [S]$ is the complete connection of $J [W]$ and the complete graph on $C$ , giving the stated join with $G^{'} = J [W]$ up to the canonical identification of its parts. This description also holds when either selected part is empty.

3.1step 1.1step 2.1F3F4∎

Apply the completion lemma to $J = G [A]$ , $W$ , and $C$ . Step 2.1 verifies its set-disjointness and cardinality hypotheses, including at $ℓ = 0$ or $ℓ = n$ . It yields an ordinary embedding $f : V (J) \to S$ into $G [S]$ . Define $h (v) = f (ι (v))$ for $v \in V (H_{2})$ . If $h (u) = h (v)$ , injectivity of $f$ and then of $ι$ gives $u = v$ ; each edge of $H_{2}$ maps through $ι$ to an edge of $J$ and then through $f$ to an edge of $G [S]$ . Hence $h$ is an ordinary embedding of $H_{2}$ into $G [S]$ and yields an ordinary copy. Every vertex of that copy lies in $S$ , whose vertices all have the same colour; hence the copy is monochromatic. Since $S$ was arbitrary among the $n$ -vertex sets in a colour class, the conclusion holds for every such set.

Depends on

Used by · 1

Join separator for equal-order targets

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 page 2, Section 3, ordinary classes, red n-vertex set