Question on Basic Graph Theorems

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

Answer: C

Explanation :

Example Method
Example 1:

P: number of add degree vertices = 2 (Even) => P is valid
Q: Sum of degrees of all vertices = 1+2+2+1 = 6 (Even) =>Q is valid

Example 2:

P: number of add degree vertices = 0 (Even) => P is valid
Q: Sum of degrees of all vertices = 2+2+2 = 6(Even) =>Q is valid





Example 3:

P: number of add degree vertices = 2 (Even) => P is valid
Q: Sum of degrees of all vertices = 2+2+3+3+2 = 12 (Even) =>Q is valid





Direct Proof Method
Prove P : Number of odd degree vertices is even.
Lets assume there are n nodes in undirected graph and n1 nodes are of add degree. This information can be put in an equation format as shown below.

We know that part C of the expression is even number as a undirected edge corresponds to 1 degree to each of the nodes attached.

B part of the expression is also even number because degrees of all vertices of Vn1+1 to Vn are even numbers.

If we observe A part of the expression, deg(Vi) for i=1 to n1 are odd numbers. To make the whole expression (A) even n1 has to be a even number.

Hence, the number of nodes (n1) of off degree are even.

Prove Q : Sum of degrees of all vertices is even. 
This property is obvious from the fact that while counting the degress of vertices, each edhe is counted twice (once at each end).

Topics to revise :
Undirected Graphs and Basic Theorems

References :
Please read Chapter 1: Introduction (Page 8) in Graph Theory by N.Deo