edited by
11,534 views
38 votes
38 votes

Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is:

  1. $12$
  2. $8$
  3. less than $8$
  4. more than $12$
edited by

4 Answers

Best answer
70 votes
70 votes

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

edited by
2 votes
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/

Answer:

Related questions

15 votes
15 votes
2 answers
1
gatecse asked Sep 21, 2014
8,216 views
Which one of the following graphs is NOT planar? G1G2G3G4
57 votes
57 votes
3 answers
2
19 votes
19 votes
3 answers
3
gatecse asked Sep 21, 2014
9,197 views
Let $G$ be a simple connected planar graph with $13$ vertices and $19$ edges. Then, the number of faces in the planar embedding of the graph is:$6$$8$$9$$13$
37 votes
37 votes
7 answers
4
Ishrat Jahan asked Oct 31, 2014
8,718 views
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is aHamiltonian cyclegri...