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

GATE 2013 · Discrete Mathematics · Degree of Graph · easy

Answer: C. Both P and Q

1. Sum of degrees is even (Q): Every edge has two endpoints, so it is counted twice in the degree total. Thus the sum equals 2|E|, which is even regardless of the graph. Statement Q is TRUE.
2. Count of odd-degree vertices is even (P): Split the degree sum into even-degree and odd-degree groups. The even group sums to an even number, and the whole sum is even, so the odd group must also sum to an even number. A sum of odd numbers is even only when there is an even count of them. Statement P is TRUE.
3. Combine the verdicts: Both P and Q hold for every undirected graph, so the correct choice is C.