complement set of edges. That is (v,w) is in E if and only if (v,w) E E Theorem Given G, the complement graph of G, G can be constructed in polynomial time Proof. To construct G construct a copy of V (linear time) and then construct E by a) constructing all possible edges of between vertices in V (effectively constructing the complete graph on the vertices V. This can be done in quadratic time in IVI b) Then traverse the adjacency list of E and delete those edges from the from the complete set of edges just constructed. This again can be done in at worse O(IVF) time. This leaves you with the set of edges of E Thus the whole procedure can be done in polynomial time Theorem: C is a vertex cover in a graph G (V, E) if and only if the set of vertices V-Cis a clique in the complement graph of G l. Proof: Ca vertex cover implies that V-C is a clique Suppose V-C is not a clique in G Then two vertices in V-C are not connected by an edge in E, thus (v,w) g E But v and w are in V-C, thus v, w are not in C, thus Cis not a vertex cover since it does not cover (v,w) Therefore Ca vertex cover implies that V-C is a clique Proof: V-C is a clique implies Ca vertex cover Suppose C is not a vertex cover for G Then there is an edge (v,w) E E where neither v nor w is in C Since v, w g C that implies that both v and w are in V-C But (v,w) in E means that (v, w) E This contradicts that V-C is a clique Therefore V-C is a clique implies C a vertex cover Theorem: Min Vertex cover and Max Clique are polynomial reducible to each other. (Thus if you can solve one problem in polynomial time you can solve the other problem in polynomial time Proof Since getting the complement graph takes only polynomial time, the transformation from G to G is polynomial time Suppose you can solve Max Clique in polynomial time. Write this max clique as a complement of some set of vertices C. that is V-C. Then C must be the smallest vertex cover in G. (If there is a smaller vertex cover, say C, then V-C would be a larger clique than V-C.) A similar argument works to show that if you can solve Min Vertex cover in polynomial time you can solve Max Clique in polynomial time