CorollaryStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-05

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.

INDEPENDENT SET and VERTEX COVER are NP-complete

Statement

INDEPENDENT SET and VERTEX COVER are NP-complete.

Facts & Assumptions

Given: Arbitrary instances $(G, k)$ of INDEPENDENT SET and VERTEX COVER.

[L1]

CLIQUE is NP-complete, by CLIQUE is NP-complete.

[L2]

CLIQUE, INDEPENDENT SET, and VERTEX COVER polynomial-time many-one reduce to one another, by CLIQUE, INDEPENDENT SET, and VERTEX COVER are polynomially interreducible.

[L3]

A language is NP-complete exactly when it is NP-hard and belongs to $N P$ , by NP-hard and NP-complete languages.

[F1]

INDEPENDENT SET asks for $k$ pairwise nonadjacent chosen vertices, and VERTEX COVER asks for at most $k$ vertices meeting every edge, by Clique, independent set, and vertex cover decision problems.

Proof

technique · direct

1.1

A certificate for INDEPENDENT SET is a list of $k$ vertices, and one checks in polynomial time that no pair among them is adjacent. A certificate for VERTEX COVER is a list of at most $k$ vertices, and one checks in polynomial time that every edge has an endpoint in that list. Hence both problems lie in $N P$ .

F1givenconstruct

1.2

Since [L1] makes CLIQUE NP-complete, every language in $N P$ reduces to CLIQUE. Applying the reductions from [L2] from CLIQUE to INDEPENDENT SET and from CLIQUE to VERTEX COVER shows that every language in $N P$ reduces to each of those target problems. Therefore both targets are NP-hard.

L1L2L3

2.1

Combine step 1.1 with step 1.2 and [L3]. Both INDEPENDENT SET and VERTEX COVER are NP-complete.

L3step 1.1step 1.2∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

11 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

Fabrizio Iozzi and Luca Trevisan, Handout NP3 (standard reference, not scraped)
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)