Question

Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then size of the maximum independent set of G is

a) more than 12
b) less than 8
c) 8
d) 12

Answer 1

Answer on Question #38340 – Math - Graph Theory

Let $G$ be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of $G$ is 8. Then size of the maximum independent set of $G$ is

a) more than 12

b) less than 8

c) 8

d) 12

Solution:

A covering with minimum number of vertices is called minimum vertex covering.

Number of vertices in it is minimum vertex number, let us say 'x'.

Independent set with max number of vertices is max vertex independent set.

Number of vertices in max vertex independent set is maximum vertex number, let us say 'y'.

So for any Graph $G: x + y = |v(G)|$.

Therefore, $8 + y = 20$.

$$y = 12.$$

Answer: d) 12