The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
1.9k views

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$
asked in Graph Theory by Boss (18.3k points)
edited by | 1.9k views

1 Answer

+35 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

answered by Loyal (5.7k points)
edited by
0
Well explained!!
+20
a set of vertices $X \subseteq V(G)$ of a graph $G$ is independent if and only if its complement $V(G) \setminus X$ is a vertex cover.   ( $V(G) \setminus X$ is complement of $X$ )
(Because if $X$ is VC, then for every edge atleast one endpoint will be in $X$. Removing $X$ from $V$ we get all nonadjacent vertices.)
Complement of vertex cover is Independent set and vice versa.
If that vertex cover is minimum, then complement is Maximum Independent set.
+3
nice explanation !!!

always searching of ur comment / answer :)
+8
vertex covering no. + vertex independent no. = no. of vertices

8 + vertex independent no. = 20

vertex independent no.= 12
+4
He he..thnks Anil :)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,976 questions
47,609 answers
146,779 comments
62,342 users