Which of the following statements is/are TRUE for undirected graphs? P: Number…
20132013
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
Attempted by 408 students.
Show answer & explanation
Correct answer: C
Key idea: use the handshaking lemma and a parity argument.
Sum of degrees = 2 × number of edges, because each edge increases the degree of two vertices by 1.
Therefore the sum of degrees is even; this proves the statement that the sum of degrees of all vertices is even.
Even-degree vertices contribute even numbers to the total, so the parity of the total sum is determined by how many vertices have odd degree. Since the total is even, there must be an even number of odd-degree vertices.
Conclusion: Both statements are true for every undirected graph.
A video solution is available for this question — log in and enroll to watch it.