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 does not contain any other vertex cover as a proper subset), but not necessarily vice versa.
Finding a minimum vertex cover of a general graph is NP-hard. The decision problem of whether a graph has a vertex cover of size at most a specified integer is NP-complete. However, for a bipartite graph, the König-Egervá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.
