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.

Clique and independence duality under complementation

Statement

For every finite simple graph $G$ , a vertex subset is independent in $G$ if and only if it is a clique in $\overline{G}$ . Thus $α (G) = ω (\overline{G})$ and $ω (G) = α (\overline{G})$ .

Statement references

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

Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree

Cliques, independent sets, clique number and independence number

Graph isomorphisms, automorphisms and graph complements

Facts & Assumptions

[F1]

A finite simple graph $G = (V, E)$ has finite vertex set $V$ and edge set $E \subseteq [V]^{2}$ , the set of unordered pairs of distinct vertices. Its complement is $\overline{G} = (V, [V]^{2} ∖ E)$ , and $\overline{\overline{G}} = G$ . A finite simple graph is a finite vertex set together with a set of two-element vertex subsets Graph isomorphisms, automorphisms and graph complements

[F2]

Distinct vertices $u, v$ are adjacent in $G = (V, E)$ exactly when ${u, v} \in E$ . A vertex subset is independent when no two of its distinct vertices are adjacent, and is a clique when every two of its distinct vertices are adjacent. The independence number $α$ and clique number $ω$ are the respective maxima of the cardinalities of these subsets; both maxima exist for finite graphs, including the empty graph. Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree Cliques, independent sets, clique number and independence number

Proof

Given: A finite simple graph $G = (V, E)$ .

Goal: Prove the stated subset equivalence and both equalities of numbers.

1.1F1F2

Let $S \subseteq V$ . Each pair of distinct vertices of $S$ is a nonedge of $G$ exactly when it is an edge of $\overline{G}$ . Therefore the condition that every such pair is a nonedge of $G$ is equivalent to the condition that every such pair is an edge of $\overline{G}$ ; this includes subsets with fewer than two vertices. Hence $S$ is independent in $G$ if and only if it is a clique in $\overline{G}$ .

2.1F1F2step 1.1∎

The independent subsets of $G$ and the cliques of $\overline{G}$ are consequently the same subsets of the same vertex set, so their sets of cardinalities and their maxima coincide: $α (G) = ω (\overline{G})$ . Applying the same equivalence to $\overline{G}$ and using $\overline{\overline{G}} = G$ gives $α (\overline{G}) = ω (G)$ .

Depends on

Used by · 1

Induced Ramsey graph with the same independence number

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.