# Minimum vertex cover

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

A minimum vertex cover has least cardinality among all vertex covers of the finite simple graph.

mko-minimum-vertex-cover · definition · v0.10.0



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

[All eight subsets for minimum cover on P3](https://ocme.evemisslab.com/en/derivations/derivation-mko-minimum-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


- [Vertex cover](https://ocme.evemisslab.com/en/mko/mko-vertex-cover/) — Qualify coverage first.
- [Optimization problem](https://ocme.evemisslab.com/en/mko/mko-optimization-problem/) — Use minimum-cardinality semantics.
- [Cardinality comparison of sets](https://ocme.evemisslab.com/en/mko/mko-cardinality-comparison/) — 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.

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