GATE 2013 CS (CS1) – Question 35

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 1 mark · Multiple choice

For undirected graphs, P: The number of odd-degree vertices is even. Q: The sum of all vertex degrees is even. Which hold?

P only
Q only
Both
Neither

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) Both

Explanation

The degree sum equals twice the edge count, so Q is true. Even-degree vertices contribute an even sum; therefore the number of odd contributions must also be even, proving P. Both statements hold, C.

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

GATE 2013 CS (CS1) Q36 – The line graph L(G) has one vertex per edge of simple G, and joins vertices iff their G…
GATE 2011 CS (CS1) Q27 – The drawings show complete graph K₄ and cube graph Q₃. Which is true?
GATE 2010 CS (CS1) Q11 – For graph G=(V,E), let (G)= di dd, where i d counts vertices of degree d. If different…
GATE 2010 CS (CS1) Q38 – Which sequences cannot be degree sequences of simple graphs? I: 7,6,5,4,4,3,2,1 II:…
GATE 2015 CS (CS2) Q61 – A self-complementary graph is isomorphic to its complement. What must its vertex count n…
GATE 2015 CS (CS2) Q62 – A bridge is an edge whose removal disconnects a connected graph. Which is true?

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →