= Minimum vertex cover
A <minimum vertex cover> is a <vertex cover> of smallest <cardinality> among all <vertex covers> of the same finite <simple graph>. The optimum size is the <vertex cover number>. By the <complement of a set> correspondence, a <minimum vertex cover> leaves a largest possible <independent set> unselected.
Minimum size is stronger than merely being unable to remove a selected <vertex>. In the <star graph> $K_{1,3}$, the three leaves form a <vertex cover> from which no <vertex> can be removed: each leaf covers its own <edge>. Nevertheless, the centre alone is a <minimum vertex cover> of size one. Such an inclusion-minimal <vertex cover> can therefore be much larger than a <minimum vertex cover>.
Back to article page
