What Conclusions may be drawn from the Handshaking theorem?
What Conclusions may be drawn from the Handshaking theorem?
Answer: A. The Sum of degrees of all vertices is always even.; B. The Sum of degrees of all vertices with odd degree is always even.; C. The number of vertices with odd degree is always even — Handshaking Theorem (key fact): the sum of the degrees of all vertices equals twice the number of edges. Reason: Each edge contributes 1 to the degree of each…
- A.
The Sum of degrees of all vertices is always even.
- B.
The Sum of degrees of all vertices with odd degree is always even.
- C.
The number of vertices with odd degree is always even
- D.
none of above
Attempted by 94 students.
Show answer & explanation
Correct answer: A, B, C
Handshaking Theorem (key fact): the sum of the degrees of all vertices equals twice the number of edges.
Reason:
Each edge contributes 1 to the degree of each of its two endpoints, so every edge contributes exactly 2 to the total degree sum. Therefore the total degree sum is 2 × (number of edges), which is even.
Consequently, the sum of degrees of all vertices is always even.
Because the sum of all degrees is even and the sum of degrees of even-degree vertices is even, the sum of degrees of odd-degree vertices must also be even.
From parity: the sum of k odd numbers is odd when k is odd and even when k is even. Since the sum of all odd-degree vertices is even, there must be an even number of odd-degree vertices.
Summary:
The sum of degrees of all vertices is always even.
The sum of degrees of vertices with odd degree is even.
The number of vertices with odd degree is even.