GATE CSE 2013 | Question: 25

Question

Which of the following statements is/are TRUE for undirected graphs?

P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.

• A.  P only
• B.  Q only
• C.  Both P and Q
• D.  Neither P nor Q

Comments

The No. of odd degree vertices in any graph is always even.

In any graph sum of degrees of vertices is twice the no of edges.

So, Both are True.

Answer 1

Both are correct

P: sum of odd degree $+$ sum of even degree$=2\times \text{no. of edges}$

sum of odd degree$=2\times \text{no. of edges - sum of even degree}$

The right hand side must be even as the difference of $2$ even numbers is always even.

Q: each edge is counted twice so sum of degree is always even

Comments

Here, we can go one step further, The sum of odd degrees vertices is EVEN.

Say, that the Odd degree vertices are of the form 2n1 -1 , 2n2 - 1, ..... , 2nk - 1 i.e 'k' such terms,

then there sum can be rearranged as 2 *  (n1 + n2 + ... + nk) - k * (1).

Now the quantity 2 *  (n1 + n2 + ... + nk) is EVEN,  Thus for the SUM to be EVEN the quantity  k * (1) must also be EVEN.

Thus we can conclude that 'k' is EVEN, i.e There are EVEN no. of Odd degree vertices.

---

yes got it

Answer 2

A and C are odd degree of vertices so number of odd degree vertices = 2 so P is True and sum = 3 + 2 +3 +2 = 10 which is even 

so P and Q are both true option C

Answer 3

In graph Theory i knew an intresting thing , that sum of degrees of all vertices are always even .