# Minimum Number of Managers

Minimum Number of Managers

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.

n

n