A vertex cover of a graph is a set of vertecies where every edge connects to at least one vertex in the set.

As a concrete example, a student club where if any two students are friends, then at least one is in the club.

Suppose the school has three students, A, B, and C. A and B are friends and A and C are friends, but B and C are not friends. One obvious vertex cover would be to have all the students in the club, {A.B.C}. Another would be just {B,C}. Another would be just {A}.

{B} would not be a vertex cover, since A and C are friends, but neither is in the club.

The optimal vertex cover is the smallest possible vertex cover. In the school friends example, {A} is the optimal vertex cover. In general, the opitmal vertex cover problem is NP-complete, which makes it a very difficult problem for large groups, and interesting problem in computer science.