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

## See also

Independence Number,

Minimum Vertex Cover,

Vertex Cover,

Vertex
Cover Polynomial
## Explore with Wolfram|Alpha

## References

West, D. B. *Introduction
to Graph Theory, 2nd ed.* Englewood Cliffs, NJ: Prentice-Hall, 2000.
## Cite this as:

Weisstein, Eric W. "Vertex Cover Number."
From *MathWorld*--A Wolfram Web Resource. https://mathworld.wolfram.com/VertexCoverNumber.html

## Subject classifications