search
Log In
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
28 votes
5.5k 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$
in Graph Theory
edited by
5.5k views
0

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

4 Answers

55 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


edited by
0
Well explained!!
45
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.
7
nice explanation !!!

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

8 + vertex independent no. = 20

vertex independent no.= 12
5
He he..thnks Anil :)
1

Useful

3 votes
$minimum\ vertex\ cover(\beta)+maximum\ independent\ set(\alpha)=n(no.\ of\ vertices)$

$8+x=20 \implies x=20-8 = 12$

$answer\ is\ A)12$
0 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/

ago
0 votes

The actual relation is given by 

 

maximum independent set(α) >= n(no. of vertices) - minimum vertex cover(β)

α >= 20-8

α >=12,    hence option A and D are both correct.

ago
Answer:

Related questions

22 votes
3 answers
1
5.4k views
How many distinct binary search trees can be created out of $4$ distinct keys? $5$ $14$ $24$ $42$
asked Sep 22, 2014 in Graph Theory Kathleen 5.4k views
12 votes
2 answers
2
4.3k views
Which one of the following graphs is NOT planar? G1 G2 G3 G4
asked Sep 21, 2014 in Graph Theory gatecse 4.3k views
46 votes
3 answers
3
5.5k views
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ iff either $j = i + 1$ or $j = 3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is $4$ $7$ $23$ $99$
asked Nov 4, 2014 in Graph Theory Ishrat Jahan 5.5k views
12 votes
3 answers
4
4.2k 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$
asked Sep 21, 2014 in Graph Theory gatecse 4.2k views
...