RemarkRemark: 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.

Figure 1: recursive construction and red witness

PDF p. 3: Figure 1, drawing and caption

Statement

In the recursive separator construction, let $k \geq 2$ and $2 \leq r \leq k$ . The finite connected simple graphs $H_{1}, H_{2}$ are non-isomorphic, each has an edge, and they are ordered by decreasing largest block order, breaking ties by decreasing vertex order. Let $I$ be the construction's independent set in $H_{2}$ , meaning that no two of its vertices are adjacent, and let $F = H_{2} - I$ be the subgraph induced by the remaining vertices. The base graph $A$ has a monochromatic induced copy of $F$ in every colouring with $k$ available colours. An induced copy retains exactly the host edges between its vertices; monochromatic means that all its vertices have the same colour.

Figure 1 schematically depicts $H = H_{2}$ decomposed into $F$ and $I$ , the core $A$ with induced copies of $F$ , and the graph $A_{r}$ formed by attaching copies of $A_{r - 1}$ according to the neighbourhoods of vertices of $I$ . For each induced-copy vertex set $S$ of $F$ in the core, the construction chooses an induced embedding $φ_{S} : F \to A$ with image $S$ and attaches one part for each $u \in I$ . An induced embedding is an injection preserving both adjacency and nonadjacency. Every vertex of that part is joined exactly to the core vertices $φ_{S} (v)$ for which $v$ is adjacent to $u$ in $H_{2}$ ; distinct parts have no edges between them.

Suppose an $r$ -colouring of $A_{r}$ uses every one of its $r$ colours in every part. Then the core has a monochromatic induced copy of $F$ . If its colour is called red, choosing one red vertex in each part corresponding to that copy and to a vertex of $I$ gives, together with the core copy, a red induced copy of $H_{2}$ , as illustrated by the highlighted vertices in Figure 1. A colouring is a function from vertices to the available colours; it need not be proper or use every colour on the whole graph.

Statement references

Recursive graphs Ar and their attachments

Neighbourhood attachments indexed by induced embeddings

A monochromatic F extends through all-colour attachments

One representative from each matching attachment reconstructs the target

Facts & Assumptions

[F1]

The recursive construction supplies the core, the chosen embedding for each induced-copy vertex set, and one disjoint part for each corresponding vertex of $I$ . Its parts and their core adjacencies follow the labelled neighbourhood-attachment rules. Recursive graphs Ar and their attachments Neighbourhood attachments indexed by induced embeddings

[F2]

Under the stated all-colours hypothesis, the core has a monochromatic induced copy of $F$ , and representatives of its colour in the corresponding parts extend it to a monochromatic induced copy of $H_{2}$ . A monochromatic F extends through all-colour attachments

[F3]

The representative lemma identifies the induced copy: its isomorphism sends each vertex of $F$ to its image in the core and each $u \in I$ to the representative in the part indexed by $u$ . One representative from each matching attachment reconstructs the target

Proof

Given: The recursive construction and an $r$ -colouring in which every part uses all $r$ colours.

Goal: Explain the red induced copy depicted in Figure 1.

1.1givenF1F2

By F2, the core contains a monochromatic induced copy of $F$ . Call its vertex set $S$ and its colour red. By F1, for the chosen embedding $φ_{S}$ there is a corresponding part for every $u \in I$ ; since each part uses every colour, select a red vertex from each such part.

2.1F1F2F3step 1.1∎

By F2, the selected vertices and $S$ induce a monochromatic copy of $H_{2}$ . More explicitly, F3 identifies the vertices of $S$ with $F$ and the selected representatives with $I$ ; the attachment rules reproduce the edges between $F$ and $I$ , and distinct parts have no edges between them. The selected vertices are all red, as required.

Extraction notes

The rendered drawing is schematic: it illustrates the construction and a red witness, and is not used to infer numerical vertex counts. The proof of the witness uses the declared suppliers rather than the figure as evidence.

Depends on

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, Figure 1 and caption; Section 3, recursive construction; PDF p. 4, first paragraph