in Graph Theory edited by
23 votes
23 votes

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.

  1.  P only
  2.  Q only
  3.  Both P and Q
  4.  Neither P nor Q
in Graph Theory edited by

1 comment

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.

2 Answers

41 votes
41 votes
Best answer
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
edited by
8 votes
8 votes

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


Related questions