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 , 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.
New to topics? Read the docs here!