GATE 2005
|
Question 11
|
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
|
12
|
|
|
8
|
|
|
Less than 8
|
|
|
More than 12
|
Question 11 Explanation:
No. of vertices = 20
Edges = 100
Minimum cover of vertex G is = 8
Maximum Independent set of G = No. of vertices – Minimum cover of vertex G
= 20 – 8
= 12
Edges = 100
Minimum cover of vertex G is = 8
Maximum Independent set of G = No. of vertices – Minimum cover of vertex G
= 20 – 8
= 12
Correct Answer: A
Question 11 Explanation:
No. of vertices = 20
Edges = 100
Minimum cover of vertex G is = 8
Maximum Independent set of G = No. of vertices – Minimum cover of vertex G
= 20 – 8
= 12
Edges = 100
Minimum cover of vertex G is = 8
Maximum Independent set of G = No. of vertices – Minimum cover of vertex G
= 20 – 8
= 12