🎴 Flashcard Mode
GATE (Computer Science & Information Technology)
Card1 / 29
Mastered0
Review0
QuestionClick to flip
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
AnswerClick to flip back
A
12
💡 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.