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.

Explore with Wolfram|Alpha

More things to try:

1->2, 2->3, 3->1, 3->4, 4->1
curl (curl F)
images of the space-filling polyhedra

Cite this as:

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

Minimal Vertex Cover

See also

Explore with Wolfram|Alpha

Cite this as:

Subject classifications