in Graph Theory
293 views
1 vote
1 vote

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
by
293 views

1 comment

any one please explain this question..

Thanks .
1
1

3 Answers

2 votes
2 votes
Best answer

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 vote
1 vote

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 vote
1 vote

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