Minimum vertex cover

Mathematical statement

For a complete bounded finite simple undirected graph enumerate every vertex subset and audit every edge to obtain minimum cardinality and all minimizing covers. A nonminimum cover needs an explicit smaller-cover witness. Inclusion-minimal means each single-vertex deletion loses coverage; it does not imply minimum cardinality. Retain edgeless graphs, multiple minimum solutions and minimal-but-nonminimum examples. Do not substitute maximality, edge covers or independent sets, or invoke Konig theorem or weighted/directed variants.

Representative formula (exact TeX)

V(G,C)=k

Assumptions

• Vertices are finite and unique; edges are loop-free duplicate-free unordered pairs.
• The vertex bound permits complete subset enumeration.

Symbol scope

• V — minimum-vertex-cover operator
• G — finite simple graph
• C — vertex cover
• k — minimum cover cardinality

Intuition, definition, and misconceptions

Qualify every vertex subset against every edge.

Return minimum size and all minimizing covers together.

Give explicit nonminimum and minimal-but-nonminimum witnesses.

Inclusion-minimal or maximal is not the same as minimum.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Vertex cover — Qualify coverage first.
• Optimization problem — Use minimum-cardinality semantics.
• Cardinality comparison of sets — Compare cover sizes.

Verification boundary

Only small finite simple graphs are exhaustively audited; no polynomial-time or approximation-ratio claim is supplied.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add the vertex-cover decision problem and approximation boundaries.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.