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.
One representative from each matching attachment reconstructs the target
Statement
Let be finite simple graphs, let be independent, and put . In the labelled neighbourhood-attachment graph constructed from these data, fix an induced embedding and, for each , choose a vertex in the part . Then the subgraph induced by the core vertices for together with the vertices for is isomorphic to . If these vertices all have one common colour in a vertex colouring, this is a monochromatic induced copy of .
Statement references
Neighbourhood attachments indexed by induced embeddings
Unrestricted finite colourings and used palettes
A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
Subgraphs, induced subgraphs and spanning subgraphs
Graph isomorphisms, automorphisms and graph complements
Induced embeddings and induced copies of a graph
Cliques, independent sets, clique number and independence number
Facts & Assumptions
In the labelled attachment construction, the core is a tagged copy of , each is disjoint from the core and the other parts, distinct parts have no edges between them, and is adjacent to exactly when for some adjacent to in . See Neighbourhood attachments indexed by induced embeddings.
An induced embedding is an injection preserving and reflecting adjacency; an induced subgraph retains exactly the ambient edges between its vertices. A graph isomorphism is a vertex bijection preserving and reflecting adjacency. See Induced embeddings and induced copies of a graph, Subgraphs, induced subgraphs and spanning subgraphs, and Graph isomorphisms, automorphisms and graph complements.
An independent set has no edge joining two distinct members. A monochromatic vertex set has one common colour on its vertices. See Cliques, independent sets, clique number and independence number and Unrestricted finite colourings and used palettes.
A function assigns exactly one value in to each element of . It is injective when implies , surjective when every element of is a value of , and bijective when both conditions hold. See A function is a relation f with (a,b) ∈ f and (a,c) ∈ f implying b = c; f : A → B, the value f(a), domain and codomain and Injection, surjection, bijection.
Proof
Given: The graphs, independent set, embedding and representatives in the statement.
Goal: Construct the stated induced isomorphism and establish the colour conclusion.
Define , where is the displayed induced subgraph, by for and for . The core vertices are distinct because is injective; the representatives are distinct because their indexed parts are disjoint, and none lies in the core. Thus is injective, and it is surjective onto by the definition of . This also covers an empty or empty .
For distinct vertices of , their images are adjacent exactly when their images under are adjacent in , equivalently when the original vertices are adjacent in , since is induced. For and , the attachment rule says and are adjacent exactly when some satisfies and ; injectivity forces . For distinct , their images lie in distinct parts and are nonadjacent, as are because is independent. These cases exhaust distinct pairs, so preserves and reflects adjacency and is an isomorphism from onto . If all vertices of have one common colour, its induced copy is monochromatic.
Depends on
- Neighbourhood attachments indexed by induced embeddings
- Unrestricted finite colourings and used palettes
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Subgraphs, induced subgraphs and spanning subgraphs
- Graph isomorphisms, automorphisms and graph complements
- Induced embeddings and induced copies of a graph
- Cliques, independent sets, clique number and independence number
- A function is a relation f with (a,b) ∈ f and (a,c) ∈ f implying b = c; f : A → B, the value f(a), domain and codomain
- Injection, surjection, bijection
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.