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

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, the size of the maximum independent set of G is: A. 12  B. 8  C. less than 8  D. more than 12

Accepted Answer

Maximum independent set size = 20 - 8 = 12, which is option A. A vertex cover and an independent set are complements of each other: a set of vertices is a vertex cover exactly when the remaining vertices form an independent set. So the largest independent set is just all the vertices left over after removing a smallest vertex cover. With 20 vertices and a minimum vertex cover of size 8, that leftover set has 20 - 8 = 12 vertices.