A group of workers (labeled 1 to ) interact in pairs, as shown by a line between them. Any worker can be a manager, and for each red line, at least one must be a manager. The task is to find a minimum number of managers. Try this heuristic: at each stage, choose a person with a maximal number of links. The special case is provided to show that this heuristic does not always work.

In graph theory, this is known as the minimum vertex cover problem.

Reference

[1] S. Permmaraju and S. Skiena, Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, New York: Cambridge University Press, 2003 pp. 317–318.