GATE 2005
March 12, 2025GATE 2005
March 12, 2025GATE 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