Alphabeta Math
LemmaStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-01
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.

ind⁡H(G)\operatorname{ind}_H(G) is isomorphism-invariant and equals ind⁡H‾(G‾)\operatorname{ind}_{\overline H}(\overline G)

Statement

If H≅H′H\cong H' and G≅G′G\cong G', then

ind⁡H(G)=ind⁡H′(G′).\operatorname{ind}_H(G)=\operatorname{ind}_{H'}(G').

Moreover,

ind⁡H(G)=ind⁡H‾(G‾).\operatorname{ind}_H(G)=\operatorname{ind}_{\overline H}(\overline G).

Facts & Assumptions

Given: Finite graphs H,H′,G,G′H,H',G,G' with isomorphisms a:H′→Ha:H'\to H and b:G→G′b:G\to G'.

[F1]

ind⁡H(G)\operatorname{ind}_H(G) is the finite cardinality of the induced-embedding set (The induced-embedding count ind⁡H(G)\operatorname{ind}_H(G)).

[F2]

Isomorphisms and induced embeddings preserve adjacency and nonadjacency in both directions (Induced embeddings and induced copies of a graph, Graph isomorphisms, automorphisms and graph complements).

Proof

technique · direct bijections
1.1

The assignment φ↦b∘φ∘a\varphi\mapsto b\circ\varphi\circ a sends induced embeddings H→GH\to G to induced embeddings H′→G′H'\to G'.

F2
1.2

The same vertex map φ\varphi is an induced embedding H→GH\to G exactly when it is an induced embedding H‾→G‾\overline H\to\overline G, because complementation reverses both adjacency tests simultaneously.

F2
2.1

Its inverse is θ↦b−1∘θ∘a−1\theta\mapsto b^{-1}\circ\theta\circ a^{-1}, so it is a bijection and the first equality follows.

step 1.1F1F2
3.1

The identity on maps is therefore a bijection between these embedding sets, proving the complement equality.

step 1.2F1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 26 results over 13 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources