Minimal Vertex Cover

A minimal vertex cover is an vertex cover of a graph that is not a proper subset of any other vertex cover.

A minimal vertex cover corresponds to the complement of maximal independent vertex set, so the counts of minimal vertex covers and maximal independent vertex sets in a graph are identical.

Every minimum vertex cover is a minimal vertex cover, but the converse does not necessarily hold.

See also

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Minimal Vertex Cover." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MinimalVertexCover.html

Subject classifications