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.
Linear realisations preserve induced pieces
Statement
Let be a finite linear hypergraph, let be a finite simple graph for each , and let be their hyperedge-indexed graph realisation. Then for every .
In particular, let be a finite simple graph and, for each , choose a bijection and put . Then each is an induced embedding of in , and is an induced copy of .
Statement references
Facts & Assumptions
In the Graph realisations with possibly different hyperedge pieces, each consists of two-element subsets of , and the edge set of is the union of the .
By Berge cycles, incidence graphs and girth, linearity means that distinct hyperedges have at most one common vertex.
By Subgraphs, induced subgraphs and spanning subgraphs, has vertex set and exactly the edges of whose endpoints lie in .
A bijection is injective and surjective by Injection, surjection, bijection. An induced embedding preserves and reflects adjacency on distinct vertices, and its image induces a copy, by Induced embeddings and induced copies of a graph.
By A finite simple graph is a finite vertex set together with a set of two-element vertex subsets, every edge of a finite simple graph is a two-element subset of its vertex set, so its endpoints are distinct.
Proof
Given: The hypergraph, pieces and realisation in the statement.
Goal: Prove for every hyperedge and establish the stated template consequence.
Fix . Every edge of belongs to and has both endpoints in ; hence .
Conversely, let . The endpoints are distinct and lie in , and the union defining supplies some with . Both vertices also lie in . If , then contains the two distinct vertices , contrary to linearity. Thus and . The two graphs have the same vertex set , so .
In the template construction, fix and distinct . The transport formula gives the forward implication from to . Conversely, if the image pair belongs to , the formula supplies an edge with the same image pair; injectivity of gives , so . Since is injective, its image pairs have distinct endpoints; by the equality just proved, this equivalence is also adjacency equivalence in . Surjectivity gives , so is an induced embedding and is its induced copy of .
Depends on
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Graph realisations with possibly different hyperedge pieces
- Berge cycles, incidence graphs and girth
- Subgraphs, induced subgraphs and spanning subgraphs
- Induced embeddings and induced copies of a graph
- Injection, surjection, bijection
Used by · 1
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.