638 views
1 votes
1 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

3 Answers

Best answer
2 votes
2 votes

If S is the vertex cover of G, then remaining vertices V-S must form an independent set
i.e Vertex Cover + Size of Max Independent Set = Total no of Vertices

Here Vertex Cover is 8 and Total no of Vertices are 20. so size of Max Independet set is 20-8 = 12

selected by
1 votes
1 votes

Vertex Cover is a subset of vertices such that these vertices cover all the edges in the graph.

That means each edge has atleast one end-point in the vertex cover.

A subset of vertices is a vertex cover iff its compliment is an Independent set.

Independent set is a subset of vertices such that no two vertices are adjacent.

So, Minm Vetex Number + Maxm Independent number = number of vertices

8 + ? =20

Therefore, ?=12

1 votes
1 votes

Independent Set

An Independent Set is a set of vertices (of a graph), such that they're not adjacent to each other in the graph.

A Maximal independent set is the maximum sized independent set.

Here, {1,5} is an independent set.

{1,4,5,6} is Maximal Independent Set.


Clique

Clique is the exact opposite of an Independent set.

Clique is a set of vertices (of a graph), such that they're all adjacent to each other in the graph.

{2,4,5,7} is a clique

 


Vertex-Cover

Vertex-cover is a set of vertices (of a graph), such that all the edges in the graph are incident on some vertex in it. In other words, the set of vertices that "cover" each edge.

Here {2,3,7} is a vertex-cover.

Source


Now, coming to the question, we can observe some things here:-

  • Maximal Independent Set + Minimal Vertex-Cover = All the vertices. (Evident from Image-1 and Image-3)

So, $8+x=20$  $=> x=12$

Option A


More:-

  • A set S is independent iff V-S is a vertex-cover.
    => If a set of vertices is vertex-cover (minimal or not) the remaining vertices together form an independent set. And vice versa.
     
  • A set S is independent in G iff S is a clique in G'. Evident from their definitions.
Answer:

Related questions

0 votes
0 votes
1 answer
2
Bikram asked Aug 8, 2016
573 views
In any undirected graph the sum of degree of all the nodesmust be even is twice the number of edges need not be evenboth A and B
1 votes
1 votes
1 answer
3
Bikram asked Aug 8, 2016
339 views
In the set of natural numbers the binary operators that are neither Associative nor Commutative areaddition subtraction multiplication ...
1 votes
1 votes
3 answers
4
Bikram asked Aug 8, 2016
389 views
According to the principle of logic, an implication and it's contrapositive must beboth true or both falseboth trueboth falsenone