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 G is known as the vertex cover number and is denoted τ(G). 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.

independence number | minimal vertex cover | minimum edge cover | vertex cover | vertex cover number