Alphabeta Math
DefinitionDefinition: AI-generatedProof: Not applicable
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 J and G 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 J in G is a function f:V(J)→V(G) that is injective, meaning f(x)=f(y) implies x=y, and preserves edges: if {x,y}∈E(J), then {f(x),f(y)}∈E(G).

An ordinary copy of J in G is a subgraph of G isomorphic to J: its vertex and edge sets are subsets of those of G, 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 G between those vertices need not belong to the copy. Conversely, an isomorphism from J to a subgraph of G is an ordinary embedding into G.

An induced embedding additionally reflects edges: for distinct x,y∈V(J), {f(x),f(y)}∈E(G) implies {x,y}∈E(J).

Justification

The edge condition and injectivity ensure that every image edge is a two-element edge of G on image vertices, so these vertices and edges form a subgraph. Regarded as a map from V(J) onto its image, f 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 J 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 V(G) and preserves edges in G, since every edge of the subgraph is an edge of G. 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

Used by · 15

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.