Explanation: Background Explanation:
Vertex cover is a set S of vertices of a graph such that each edge of the graph is incident to at least one vertex of S.
Independent set of a graph is a set of vertices such that none of the vertices in this set have an edge connecting them i.e. no two are adjacent. A single vertex is an independent set, but we are interested in maximum independent set, that is largest set which is independent set.
Relation between Independent Set and Vertex Cover : An interesting fact is, the number of vertices of a graph is equal to its minimum vertex cover number plus the size of a maximum independent set. How? removing all vertices of minimum vertex cover leads to maximum independent set.
So if S is the size of minimum vertex cover of G(V,E) then the size
of maximum independent set of G is |V| – S.
size of minimum vertex cover = 8
size of maximum independent set = 20 – 8 =12
Therefore, correct answer is (A).
Reference : https://www.geeksforgeeks.org/gate-gate-cs-2005-question-11/