-- Apr 24 In-Class Exercise
1) for any n >=1 , add one more vertex that is connected to all n many vertices, and such a graph will have vertex cover of size 1 ; 2) for the reduction from CLIQUE to VERTEX-COVER to work, it takes a) complement of original G, and b) compute the vertex-cover size of |V|-k for this complement graph in a). Given an adjacent matrix, finding complement graph of G can be completed in polynomial time or O(n^2), so can its vertex-cover with size of |V|-k. All in all, this is p-time isomorphism; 3) Clique size of n for |V| = n + 1 will map to this graph.
(
Edited: 2019-05-14)
1) for any n >=1 , add one more vertex that is connected to all n many vertices, and such a graph will have vertex cover of size 1 ; 2) for the reduction from CLIQUE to VERTEX-COVER to work, it takes a) complement of original G, and b) compute the vertex-cover size of |V|-k for this complement graph in a). Given an adjacent matrix, finding complement graph of G can be completed in polynomial time or O(n^2), so can its vertex-cover with size of |V|-k. All in all, this is p-time isomorphism; 3) Clique size of n for |V| = n + 1 will map to this graph.