Skip to content
GATETECH
Official PYQ · 2005Q11Graphs: Connectivity, Matching, ColouringMCQ1 mark

GATE CS 2005 Q11 — Graphs: Connectivity, Matching, Colouring

Explain with AI

Let GG be a simple graph with 2020 vertices and 100100 edges. The size of the minimum vertex cover of G is 88. Then, the size of the maximum independent set of GG is:

Choose one option
View worked solution

Answer: A

This problem is solved using the fundamental relationship between the vertex cover and the independent set of a graph.

For any graph G=(V,E)G = (V, E), a subset of vertices S⊆VS \subseteq V is an independent set if and only if its complement V∖SV \setminus S is a vertex cover. Therefore, the size of the maximum independent set (α\alpha) and the size of the minimum vertex cover (β\beta) satisfy:

α+β=∣V∣\alpha + \beta = |V|

Given:

  • Total vertices, ∣V∣=20|V| = 20
  • Size of the minimum vertex cover, β=8\beta = 8

Substituting these values:

α+8=20  ⟹  α=12\alpha + 8 = 20 \implies \alpha = 12

Thus, the size of the maximum independent set is 12.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Graphs: Connectivity, Matching, Colouring questions