293 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

### 1 comment

any one please explain this question..

Thanks .

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

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

### 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.