A minimum vertex cover is a vertex cover having the smallest possible number of vertices for a given graph. The size of a minimum vertex
cover of a graph
is known as the vertex cover number and is
denoted .

Every minimum vertex cover is a minimal vertex cover (i.e., a vertex cover that is not a proper subset of any other cover), but not necessarily
vice versa.

Finding a minimum vertex cover of a general graph is an NP-complete problem . However, for a bipartite graph , the
König-Egeváry theorem allows
a minimum vertex cover to be found in polynomial time.

A minimum vertex cover of a graph can be computed in the Wolfram Language using FindVertexCover [g ].
There is currently no Wolfram Language
function to compute all minimum vertex covers.

Minimum vertex covers correspond to the complements of maximum
independent vertex sets .

See also Independence Number ,

Minimal Vertex Cover ,

Minimum Edge Cover ,

Vertex
Cover ,

Vertex Cover Number
Explore with Wolfram|Alpha
References Pemmaraju, S. and Skiena, S. "Minimum Vertex Cover." §7.5.2 in Computational
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge,
England: Cambridge University Press, p. 317, 2003. Skiena, S. "Minimum
Vertex Cover." §5.6.2 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, p. 218, 1990. West, D. B. Introduction
to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
Cite this as:
Weisstein, Eric W. "Minimum Vertex Cover."
From MathWorld --A Wolfram Web Resource. https://mathworld.wolfram.com/MinimumVertexCover.html

Subject classifications