LemmaStatement: AI-generatedProof: 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.

Avoidance using separated palettes and anticomplete attachments

Statement

Let $G$ and $J$ be finite simple graphs, with $J$ nonempty and connected. Suppose $V (G)$ is the disjoint union of a base set $B$ and attachment sets $P_{t}$ , and no edge of $G$ joins distinct attachment sets. Let $c$ be a finite vertex colouring such that every vertex of $B$ has one fixed colour and every vertex in an attachment set has a different colour from that fixed colour. If $G [B]$ contains no induced copy of $J$ and each coloured $G [P_{t}]$ contains no monochromatic induced copy of $J$ , then the coloured graph $G$ contains no monochromatic induced copy of $J$ . Edges between $B$ and the attachment sets are unrestricted.

Statement references

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

Subgraphs, induced subgraphs and spanning subgraphs

Connected graphs and connected components defined by the existence of vertex paths

Induced embeddings and induced copies of a graph

Unrestricted finite colourings and used palettes

Facts & Assumptions

[F1]

A finite simple graph has a finite vertex set and edges that are two-element subsets of it. For a vertex subset $S$ , the induced subgraph $G [S]$ has vertex set $S$ and precisely the edges of $G$ with both endpoints in $S$ . A finite simple graph is a finite vertex set together with a set of two-element vertex subsets Subgraphs, induced subgraphs and spanning subgraphs

[F2]

A connected graph is nonempty and any two of its vertices are joined by a path, a finite list of distinct vertices with consecutive vertices adjacent. Connected graphs and connected components defined by the existence of vertex paths Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges

[F3]

An induced embedding is an injective vertex map preserving and reflecting adjacency; its image induces a copy of the source graph. An edge-preserving injective map also gives a subgraph on its image vertices and image edges. Induced embeddings and induced copies of a graph Ordinary embeddings as injections preserving edges

[F4]

A finite colouring assigns one colour to each vertex. A vertex set is monochromatic when all its vertices receive the same colour. Unrestricted finite colourings and used palettes

[F5]

If a graph's vertices are partitioned into parts with no edges between distinct parts, every connected subgraph has all its vertices in one part. Connected subgraphs cannot cross anticomplete parts

Proof

Given: The graphs, partition, colouring and avoidance hypotheses in the statement.

Goal: Show that $G$ has no monochromatic induced copy of $J$ .

1.1givenF1F3F4

Suppose that an induced embedding $f$ of $J$ into $G$ has monochromatic image $X$ . Since $J$ is nonempty, choose a vertex of $X$ . If its colour is the fixed base colour, every vertex of $X$ has that colour and therefore lies in $B$ . The same map is then an induced embedding into $G [B]$ , because $G [B]$ retains exactly the ambient edges between vertices of $B$ . This contradicts the assumed absence of an induced $J$ in $G [B]$ .

2.1givenF1F2F3F4F5step 1.1∎

Otherwise the common colour differs from the base colour, so $X$ is contained in the union $A$ of the attachment sets. The image vertices and image edges of $J$ form a connected subgraph of $G [A]$ : images of paths in $J$ are paths because $f$ is injective and preserves edges. The nonempty attachment sets partition $A$ , and no edge of $G [A]$ joins distinct parts. By the locality fact, $X$ lies in one $P_{t}$ . The map $f$ is then an induced embedding into $G [P_{t}]$ , and its image is monochromatic, contrary to the avoidance hypothesis for that attachment. Both possible colours lead to contradictions, so no such copy exists.

Depends on

Used by · 1

Inductive colouring avoiding H1

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.