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.
