LemmaStatement: AI-generatedProof: AI-generated

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.

Complementation transports induced copies on fixed vertices

Statement

Let $J$ and $G$ be finite simple graphs. An injection $f : V (J) \to V (G)$ is an induced embedding of $J$ into $G$ if and only if it is an induced embedding of $\overline{J}$ into $\overline{G}$ . For any fixed finite vertex-colouring of $G$ , the same map and vertex set transport monochromatic induced copies in either direction between these two pairs of graphs. Complementation is an involution on finite simple graphs.

Statement references

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Induced embeddings and induced copies of a graph

Graph isomorphisms, automorphisms and graph complements

Unrestricted finite colourings and used palettes

Injection, surjection, bijection

Subgraphs, induced subgraphs and spanning subgraphs

Facts & Assumptions

Given: Finite simple graphs $J$ and $G$ , an injection $f : V (J) \to V (G)$ , and a finite vertex-colouring $c$ of $G$ .

Goal: Prove the embedding equivalence, the monochromatic-copy correspondence, and the complementation involution.

[F1]

An induced embedding is an injection preserving and reflecting adjacency for every pair of distinct vertices; its image induces a copy of the domain graph (Induced embeddings and induced copies of a graph).

[F2]

The complement has the same vertices, and a pair of distinct vertices is an edge of the complement exactly when it is not an edge of the original graph (Graph isomorphisms, automorphisms and graph complements).

[F3]

A vertex-colouring is a function on the vertex set; a subset is monochromatic exactly when all its vertices have the same colour (Unrestricted finite colourings and used palettes).

[F4]

For every vertex subset $W$ of $G$ , $\overline{G [W]} = \overline{G} [W]$ (G[W]=Ḡ[W] for every vertex set W).

[F5]

A finite simple graph is determined by its vertex set and its set of edges, each of which is an unordered pair of distinct vertices (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets).

[F6]

An injection $f : A \to B$ satisfies $f (x) = f (y) \Rightarrow x = y$ for $x, y \in A$ ; its image is $f [A] = {f (x) : x \in A}$ (Injection, surjection, bijection).

[F7]

For $W \subseteq V (G)$ , the induced subgraph is $G [W] = (W, E (G) \cap [W]^{2})$ , where $[W]^{2}$ is the set of unordered pairs of distinct vertices of $W$ (Subgraphs, induced subgraphs and spanning subgraphs).

Proof

technique · direct

1.1givenF1F2F6

Complementation leaves vertices fixed. For each distinct $x, y \in V (J)$ , injectivity makes $f (x)$ and $f (y)$ distinct. If $f$ is induced from $J$ to $G$ , then $x y \in E (\overline{J})$ if and only if $x y \notin E (J)$ , if and only if $f (x) f (y) \notin E (G)$ , if and only if $f (x) f (y) \in E (\overline{G})$ . Thus $f$ is induced from $\overline{J}$ to $\overline{G}$ .

2.1F2F5step 1.1

For any finite simple graph, complementing twice leaves its vertex set fixed and restores membership of every pair of distinct vertices in its edge set. These are all possible edges, so the twice-complemented graph equals the original. Applying step 1.1 to $\overline{J}$ and $\overline{G}$ gives the converse embedding implication.

3.1F1F2F3F4F6F7step 1.1step 2.1∎

Put $W = f (V (J))$ . The equivalence above uses the same injection and image $W$ in both ambient graphs; moreover, $\overline{G [W]} = \overline{G} [W]$ . The colouring $c$ has the same domain in $G$ and $\overline{G}$ , so $W$ is monochromatic in one exactly when it is monochromatic in the other. Hence the corresponding induced copies are monochromatic together, completing all claims.

Depends on

Used by · 3

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.