# Vertex cover

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

A vertex subset C covers a finite simple undirected graph if every edge has at least one endpoint in C.

mko-vertex-cover · definition · v0.10.0



## 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

[Vertex covers and deletion certificates on a star](https://ocme.evemisslab.com/en/derivations/derivation-mko-vertex-cover-01/)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](https://ocme.evemisslab.com/en/mko/mko-graph/) — Use the finite simple graph convention.
- [Subset](https://ocme.evemisslab.com/en/mko/mko-subset/) — Candidates are vertex subsets.
- [Quantifiers and explicit domains](https://ocme.evemisslab.com/en/mko/mko-quantifier/) — 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.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/vertex-cover.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-vertex-cover/index.md)