Alphabeta Math
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.

One representative from each matching attachment reconstructs the target

Statement

Let J,A,L be finite simple graphs, let I⊆V(J) be independent, and put F=J[V(J)∖I]. In the labelled neighbourhood-attachment graph constructed from these data, fix an induced embedding φ:F→A and, for each u∈I, choose a vertex xu in the part Pφ,u. Then the subgraph induced by the core vertices (0,φ(v)) for v∈V(F) together with the vertices xu for u∈I is isomorphic to J. If these vertices all have one common colour in a vertex colouring, this is a monochromatic induced copy of J.

Facts & Assumptions

[F1]

In the labelled attachment construction, the core is a tagged copy of A, each Pφ,u is disjoint from the core and the other parts, distinct parts have no edges between them, and x∈Pφ,u is adjacent to (0,a) exactly when a=φ(v) for some v∈V(F) adjacent to u in J. See Neighbourhood attachments indexed by induced embeddings.

[F2]

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.

[F3]

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.

[F4]

A function f:X→Y assigns exactly one value in Y to each element of X. It is injective when f(x)=f(y) implies x=y, surjective when every element of Y is a value of f, 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.

1.1givenF1F2F4

Define f:V(J)→V(H), where H is the displayed induced subgraph, by f(v)=(0,φ(v)) for v∈V(F)=V(J)∖I and f(u)=xu for u∈I. 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 f is injective, and it is surjective onto V(H) by the definition of H. This also covers an empty I or empty V(F).

2.1F1F2F3F4step 1.1∎

For distinct vertices of F, their images are adjacent exactly when their images under φ are adjacent in A, equivalently when the original vertices are adjacent in J, since F is induced. For v∈V(F) and u∈I, the attachment rule says f(v) and f(u) are adjacent exactly when some w∈V(F) satisfies φ(w)=φ(v) and uw∈E(J); injectivity forces w=v. For distinct u,u′∈I, their images lie in distinct parts and are nonadjacent, as are u,u′ because I is independent. These cases exhaust distinct pairs, so f preserves and reflects adjacency and is an isomorphism from J onto H. If all vertices of H have one common colour, its induced copy is monochromatic.

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.