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.

Independence is monotone under induced embeddings

Statement

Let $J$ and $G$ be finite simple graphs. If $J$ has an induced embedding into $G$ , then $α (J) \leq α (G)$ . In particular, $α (G) < α (J)$ excludes an induced copy of $J$ in $G$ .

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

Cliques, independent sets, clique number and independence number

Facts & Assumptions

[F1]

An induced embedding is an injection on vertices that preserves adjacency and nonadjacency between distinct vertices; an induced copy arises from such an embedding. See Induced embeddings and induced copies of a graph.

[F2]

An independent set has no adjacent distinct vertices. For a finite simple graph, its independence number is the maximum cardinality of an independent vertex set, and this maximum is attained. See Cliques, independent sets, clique number and independence number.

[F3]

A bijection from a finite set to another set makes their cardinalities equal. See The cardinality | A| of a finite set.

[F4]

An injection satisfies $f (x) = f (y) \Rightarrow x = y$ ; a surjection takes every value in its codomain; a bijection has both properties. The image $f (S)$ consists of the values $f (s)$ for $s \in S$ . See Injection, surjection, bijection.

Proof

Given: Finite simple graphs $J$ and $G$ and an induced embedding $f : V (J) \to V (G)$ .

Goal: Show $α (J) \leq α (G)$ and the stated exclusion of an induced copy.

1.1F1F2F4choose

Choose an independent set $S \subseteq V (J)$ with $∣ S ∣ = α (J)$ . If two distinct vertices of $f (S)$ were adjacent, their distinct preimages in $S$ would be adjacent by the defining equivalence for an induced embedding, contrary to independence. Thus $f (S)$ is independent in $G$ .

2.1F1F2F3F4step 1.1∎

The restriction $f : S \to f (S)$ is injective because $f$ is injective, and it is surjective by the definition of $f (S)$ . Hence it is a bijection, so $∣ f (S) ∣ = ∣ S ∣ = α (J)$ . By maximality of $α (G)$ , $α (J) \leq α (G)$ . Consequently, if $α (G) < α (J)$ , no induced embedding, and hence no induced copy of $J$ in $G$ , can exist.

Depends on

Used by · 1

Independence gap for the join of components

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.