# TADM2E 5.15

From Algorithm Wiki

To build a vertex cover, we need to keep **at least** one vertex for each edge. The independent set requires **at most** one vertex for each edge.

Together it means we need to keep only **exactly** one vertex for each edge, this reduces to two-colour graph problem.