Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is …
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2017 Set 1 · Q20
Time
Your answerNumerical answer
Solution
Official answer: 18 (±0)
Discrete MathematicsA tree with vertices always contains exactly edges. For :
By the Handshaking Lemma (degree sum formula), the sum of the degrees of all vertices in any undirected graph is twice the number of edges:
Thus, the sum of the degrees of all the vertices in is 18.
Try the question first, then check your work.
Examiner trap
Recall the relationship between the number of vertices and edges in a tree, and apply the Handshaking Lemma.
This Discrete Mathematics previous year question is Q20 of the GATE CSE 2017 Set 1 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 1 has 4.
How GATE tests Discrete MathematicsIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.