Vertex cover

Mathematical statement

Declare finite unique vertices and loop-free duplicate-free unordered edges. Audit every edge; one edge with neither endpoint in C refutes coverage. The empty set covers an edgeless graph, isolated vertices are optional and any superset of a cover remains a cover. Inclusion-minimal means every single vertex deletion destroys coverage; minimum means least cardinality among all covers. Do not conflate those notions or substitute edge cover, independent set or directed-cover conventions. Minimum size is not automatically solved by the basic definition.

Representative formula (exact TeX)

V(G,C)=1

Assumptions

• Edges are canonical sorted unordered pairs, and the candidate is a unique subset of the vertex set.
• The minimum boundary exhaustively enumerates subsets only for a complete bounded small graph.

Symbol scope

• V — vertex-cover predicate
• G — finite simple graph
• C — candidate vertex subset

Intuition, definition, and misconceptions

Check at least one selected endpoint on every edge.

An uncovered edge is an explicit refuting witness.

Separate empty/isolated/superset and minimal/minimum boundaries.

Most covered edges are not all edges, and inclusion-minimal is not necessarily 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

• Finite simple undirected graphs — Use the finite simple graph convention.
• Subset — Candidates are vertex subsets.
• Quantifiers and explicit domains — Every edge has an obligation.

Verification boundary

This slice checks covers and bounded boundary cases only; the general minimum-vertex-cover node remains later work.

not_formalized

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

Next obligation

Add minimum vertex cover.

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.