LemmaStatement: AI-adaptedProof: AI-generatedprecheck 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)$ is isomorphism-invariant and equals ${ind}_{\overline{H}} (\overline{G})$

Statement

If $H ≅ H^{'}$ and $G ≅ G^{'}$ , then

${ind}_{H} (G) = {ind}_{H^{'}} (G^{'}) .$

Moreover,

${ind}_{H} (G) = {ind}_{\overline{H}} (\overline{G}) .$

Facts & Assumptions

Given: Finite graphs $H, H^{'}, G, G^{'}$ with isomorphisms $a : H^{'} \to H$ and $b : G \to G^{'}$ .

[F1]

${ind}_{H} (G)$ is the finite cardinality of the induced-embedding set (The induced-embedding count ${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 $φ \mapsto b \circ φ \circ a$ sends induced embeddings $H \to G$ to induced embeddings $H^{'} \to G^{'}$ .

1.2

The same vertex map $φ$ is an induced embedding $H \to G$ exactly when it is an induced embedding $\overline{H} \to \overline{G}$ , because complementation reverses both adjacency tests simultaneously.

2.1

Its inverse is $θ \mapsto b^{- 1} \circ θ \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 · two levels

9 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Swastik Kopparty, Local Structure: Subgraph Counts I (standard reference, not scraped)

ind⁡H(G)indH​(G) is isomorphism-invariant and equals ind⁡H‾(G‾)indH​(G)