Which of the following statement(s) is/are correct regarding about the…
2021
Which of the following statement(s) is/are correct regarding about the undirected graph?
I. Number of odd degree vertices is even.
II. Sum of degrees of all vertices is even.
Answer: C. Both I and II — This is based on the Handshaking Lemma in graph theory. Statement II: The sum of degrees of all vertices in an undirected graph is always: Sum of…
- A.
Only I
- B.
Only II
- C.
Both I and II
- D.
Neither I nor II
Attempted by 270 students.
Show answer & explanation
Correct answer: C
This is based on the Handshaking Lemma in graph theory.
Statement II:
The sum of degrees of all vertices in an undirected graph is always:
Sum of degrees=2×(number of edges
Since this is a multiple of 2, the sum is always even. ✔️
Statement I:
Because the total sum of degrees is even, the number of vertices having odd degree must be even (otherwise sum would be odd). ✔️