Given below are two statements Statement I: In an undirected graph, number of…
2021
Given below are two statements
Statement I: In an undirected graph, number of odd degree vertices is even.
Statement II: In an undirected graph, sum of degrees of all vertices is even.
In light of the above statements, choose the correct answer from the options given below.
- A.
Both Statement I and Statement II are true.
- B.
Both Statement I and Statement II are false.
- C.
Statement I is true but Statement II is false.
- D.
Statement I is false but Statement II is true.
Attempted by 350 students.
Show answer & explanation
Correct answer: A
Answer: Both statements are true.
Reason 1 (sum of degrees): In any undirected graph each edge contributes 1 to the degree of two vertices, so the total sum of degrees equals 2 × (number of edges). Therefore the sum of degrees is even.
Reason 2 (number of odd-degree vertices): Let k be the number of vertices with odd degree. The parity (even or odd) of the total sum of degrees equals the parity of k, because even-degree vertices contribute an even amount and odd-degree vertices contribute an odd amount. Since the total sum is even (from Reason 1), k must be even. Thus the number of odd-degree vertices is even.
Conclusion: Both statements are true — the handshake lemma gives an even total degree, and parity implies an even number of odd-degree vertices.
A video solution is available for this question — log in and enroll to watch it.