Let G be a simple graph with 20 vertices and 100 edges. The size of the…
2005
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
- A.
12
- B.
8
- C.
Less than 8
- D.
More than 12
Attempted by 100 students.
Show answer & explanation
Correct answer: A
Key idea: the complement of a vertex cover is an independent set.
Let n be the number of vertices. Here n = 20.
Let τ be the size of a minimum vertex cover. Given τ = 8.
The complement of a minimum vertex cover is an independent set of size n − τ = 20 − 8 = 12.
Therefore the size of the maximum independent set is 12.
A video solution is available for this question — log in and enroll to watch it.