Graph HW3

The notation graph $G=(V,E)$ means the graph has vertex set $V$ and edge set $E$.

1. A vertex cover of a graph $(V,E)$ is a subset $V'$ of vertices so that every edge in the graph contains at least one vertex from $V'$. Given a graph, produce a minimum size vertex cover for it.

2. An independent set of a graph is a subset $W$ of the vertices so that no edge contains both vertices from $W$.

   Implement an efficient algorithm for deciding whether a graph has a vertex cover that is also an independent set.