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.