# Difference between revisions of "TADM2E 5.15"

From Algorithm Wiki

(Created page with "This reduces to two-colour graph problem.") |
|||

Line 1: | Line 1: | ||

− | + | 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. |

## Latest revision as of 01:36, 1 January 2017

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.