A

vertex cover is a

set of

vertices in a

graph such that every

edge in the graph is

incident (connected) to at least one vertex in the set. The set of all vertices, for example, is a vertex cover

The vertex cover problem is: given a graph and an integer k, is there a vertex cover for the graph with <= k vertices?

It has been proven that the vertex cover problem is NP-complete. However, it is possible to answer the vertex cover problem for bipartite graphs in polynomial time.