"**No. of edges is 100**" (This information is not needed for solving this question).

Dark Mode

65 votes

Best answer

Vertex cover: A set of vertices such that each edge of the graph is incident to at least one vertex of the set.

Therefore, removing all the vertices of the vertex cover from the graph results in an isolated graph and the same set of nodes would be the independent set in the original graph.

Size of minimum vertex cover $= 8$

Size of maximum independent set $= 20 - 8 =12$

Therefore, correct answer would be (**A**).

Reference :- http://mathworld.wolfram.com/MaximumIndependentVertexSet.html

2 votes

**Answer:** **(A)**

**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.

**Solution:**

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/