Multiple choice

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

  1. 12

  2. 8

  3. less than 8

  4. more than 12
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

For any graph with n vertices, the size of the minimum vertex cover (k) and the size of the maximum independent set (alpha) satisfy the relation: k + alpha = n. Given n = 20 and k = 8, then alpha = 20 - 8 = 12.

Keep practicing — related questions