GATE CS 2026 (Forenoon) — Question 47

Discrete MathematicsAdvanced Graph Bounds (Matching, Coloring Theorems)MSQ2 marksHard

Let \( G(V, E) \) be a simple, undirected graph. A vertex cover of \( G \) is a subset \( V' \subseteq V \) such that for every \( (u, v) \in E \), \( u \in V' \) or \( v \in V' \). Let the size of the smallest vertex cover in \( G \) be \( k \). Let \( S \) be any vertex cover of size \( k \). For a vertex \( v \in V \), which of the following constraints will always ensure that \( v \in S \)?
  1. A
    The degree of \( v \) is at least \( k + 1 \)
  2. B
    The vertex \( v \) is on a path of length \( k + 1 \)
  3. C
    The vertex \( v \) is on a cycle of length \( k + 1 \)
  4. D
    The vertex \( v \) is a part of a clique of size \( k \)
Practise the full 2026-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAPractise this subject in the exam simulatorTimed, GATE-style tests with analytics that find your weak topics.
Practise more on Advanced Graph Bounds (Matching, Coloring Theorems)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group