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.
Ordinary embeddings as injections preserving edges
Definition
Let and be finite simple graphs: each has a finite vertex set and a set of edges, each edge being a two-element subset of its vertex set. An ordinary embedding of in is a function that is injective, meaning implies , and preserves edges: if , then .
An ordinary copy of in is a subgraph of isomorphic to : its vertex and edge sets are subsets of those of , and an isomorphism is a bijection of vertex sets preserving and reflecting edges. An ordinary embedding gives a copy on its image vertices using exactly its image edges; extra edges of between those vertices need not belong to the copy. Conversely, an isomorphism from to a subgraph of is an ordinary embedding into .
An induced embedding additionally reflects edges: for distinct , implies .
Justification
The edge condition and injectivity ensure that every image edge is a two-element edge of on image vertices, so these vertices and edges form a subgraph. Regarded as a map from onto its image, is bijective. It preserves edges by construction, and it reflects edges of this subgraph because each such edge is the image of an edge of and injectivity identifies its two preimages. Hence it is an isomorphism onto that subgraph. Conversely, the vertex bijection of an isomorphism onto a subgraph is injective into and preserves edges in , since every edge of the subgraph is an edge of . Thus the definition agrees with the copy formulation. The additional reverse implication is precisely the edge-reflection condition in the definition of an induced embedding.
Depends on
- 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
- 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
- Injection, surjection, bijection
- Induced embeddings and induced copies of a graph
Used by · 15
- Graph and colouring conventions
- Ordinary vertex-Ramsey class
- Edge-Ramsey class terminology in the motivation
- The k=1 case
- Complete-graph separator when orders differ
- Orienting equal-order non-isomorphic targets
- Completion inside the join separator
- Ordering targets and excluding H1 from H2
- Block exclusion in the high-girth base graph
- Rigidity of mutual ordinary embeddings
- Transport, restriction and relabelling of finite colourings
- Connected subgraphs cannot cross anticomplete parts
- Completing a restricted target with universal clique vertices
- Avoidance using separated palettes and anticomplete attachments
- Block containment and monotonicity under subgraphs
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.