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).
