Vertex Cover

You are given an undirected graph $G = (V, E)$ containing $N$ nodes and $M$ edges. The nodes are numbered from 1 to $N$. A subset $C$ of $V$ is a *vertex cover* if for every edge $(u, v) \in E$, at least one of $u$ and $v$ belong to $C$. Note that $C = V$ is always a vertex cover. Consider a partition of $V$ into two sets $A$ and $B$. It is said to be a *valid* partition if the following two cond