G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is …
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2017 Set 2 · Q23
Time
Your answerNumerical answer
Solution
Official answer: 16 (±0)
Discrete MathematicsAccording to the Handshaking Lemma, the sum of degrees of all vertices in an undirected graph equals twice the number of edges:
Given that the degree of every vertex is at least , i.e., for all :
Substituting the total sum of degrees:
For , we can have vertices of degree and vertices of degree :
Since the number of odd-degree vertices is even (), such a graph can exist.
Thus, the maximum possible value of is 16.
Try the question first, then check your work.
Examiner trap
Apply the Handshaking Lemma: , and use the condition .
This Discrete Mathematics previous year question is Q23 of the GATE CSE 2017 Set 2 paper. Find more GATE CSE PYQs on Discrete Mathematics in Engineering Mathematics, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Discrete Mathematics PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Discrete Mathematics has 50 GATE CSE PYQs across 23 papers from 2011 to 2026. 10 of them are 1-mark NAT questions like this one, and GATE CSE 2017 Set 2 has 3.
How GATE tests Discrete MathematicsIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.