The vertex cover number is the size of a minimum vertex cover in a graph is known as the vertex cover number of , denoted .
The König-Egeváry theorem states that the matching number (i.e., size of a maximum independent edge set) and vertex cover number are equal for a bipartite graph.
The independence number of a graph and vertex cover number are related by
where is the vertex count (West 2000).