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.

A monochromatic F extends through all-colour attachments

PDF p. 3: Section 3, final paragraph; PDF p. 4: Section 3, first paragraph

Statement

Use the recursive separator construction with $k \geq 2$ , non-isomorphic finite connected simple graphs $H_{1}, H_{2}$ each having an edge and ordered by decreasing largest block order, breaking ties by decreasing vertex order. Let $I$ be its chosen independent set of $H_{2}$ , let $F = H_{2} - I$ be the induced graph on the remaining vertices, and let $A$ be its core graph: every colouring of $V (A)$ with $k$ available colours has a monochromatic induced copy of $F$ . For $2 \leq r \leq k$ , form $A_{r}$ with a core copy of $A$ and a part $H_{φ_{S}, u, r - 1}$ for each induced-copy vertex set $S$ of $F$ in $A$ and each $u \in I$ , indexed by the construction's chosen induced embedding $φ_{S} : F \to A$ with image $S$ .

Suppose $c : V (A_{r}) \to {1, \dots, r}$ is a colouring in which every part uses all $r$ colours. Then the core contains a monochromatic induced copy of $F$ . For any such vertex set $S$ , write its colour as $a$ and choose, for each $u \in I$ , a vertex of colour $a$ from $H_{φ_{S}, u, r - 1}$ . These vertices together with the core copy of $S$ induce a monochromatic copy of $H_{2}$ in $A_{r}$ .

An independent set has no edge between two of its vertices. An induced embedding is an injective vertex map preserving and reflecting adjacency; an induced copy has exactly the host edges between its vertices. A colouring is an unrestricted function into the specified palette, and a vertex set is monochromatic when all its vertices receive the same colour.

Statement references

Recursive graphs Ar and their attachments

The independent set I and remainder F

Neighbourhood attachments indexed by induced embeddings

Induced vertex-Ramsey class

Fewer colours for the base graph

One representative from each matching attachment reconstructs the target

Unrestricted finite colourings and used palettes

Induced embeddings and induced copies of a graph

Facts & Assumptions

[F1]

The recursive construction supplies the stated core $A$ , the independent set $I$ , the induced remainder $F$ , and, for each induced-copy vertex set $S$ and each $u \in I$ , a part indexed by the chosen embedding $φ_{S}$ . Its graph is obtained, up to the construction's vertex relabelling, by retaining the core and these chosen parts as an induced subgraph of the full labelled neighbourhood-attachment graph. Recursive graphs Ar and their attachments The independent set I and remainder F Neighbourhood attachments indexed by induced embeddings

[F2]

The base graph has the induced $k$ -colour Ramsey property for $F$ ; colour monotonicity gives the induced $r$ -colour Ramsey property when $1 \leq r \leq k$ . This means every function from its vertices to the $r$ -colour palette has a monochromatic induced copy of $F$ . Recursive graphs Ar and their attachments Fewer colours for the base graph Induced vertex-Ramsey class

[F3]

In the full labelled neighbourhood-attachment graph, one vertex chosen from each part indexed by a fixed induced embedding and a vertex of the independent set, together with the image of the remainder in the core, induces a copy of the target. If all selected vertices have a common colour, the copy is monochromatic. One representative from each matching attachment reconstructs the target Induced embeddings and induced copies of a graph

[F4]

A colouring is a function into its palette; a part uses a colour exactly when some vertex of that part has that value. Restricting the function to the core retains its values. Unrestricted finite colourings and used palettes

Proof

Given: The construction and colouring in the statement, with $2 \leq r \leq k$ and every part using all $r$ colours.

Goal: Find a monochromatic induced copy of $F$ in the core and show that the specified representatives extend any such copy to a monochromatic induced copy of $H_{2}$ .

1.1givenF1F2F4

Restrict $c$ to the core and transport it along the core copy of $A$ to an $r$ -colouring of $A$ . By F2, there is an induced-copy vertex set $S$ of $F$ on which this colouring is constant, say with value $a \in {1, \dots, r}$ . The same conclusion applies to any monochromatic induced-copy vertex set $S$ in the core.

2.1givenF1F3F4step 1.1∎

Fix such an $S$ . By F1, the construction has chosen an induced embedding $φ_{S}$ with image $S$ and retains the corresponding part for every $u \in I$ . Each such part uses $a$ by the given hypothesis, so choose a vertex of colour $a$ in it; if $I$ is empty no choices are needed. Apply F3 to $H_{2}$ , $I$ , $F$ , $A$ and $φ_{S}$ in the full labelled attachment graph. The core image and chosen vertices induce a copy of $H_{2}$ there. All these vertices lie in the retained induced subgraph, so their mutual adjacencies are unchanged in $A_{r}$ after relabelling. They all have colour $a$ , giving the required monochromatic induced copy.

Depends on

Used by · 2

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, final paragraph; PDF p. 4, Section 3, first paragraph