Exercise 1096Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026
An even number of odd vertices
#pigeonhole#graph#parity
Statement
Show that in any graph, the number of vertices of odd degree is even.
Hint
Sum of degrees = is even.
Show solutionHide solution
Solution
Degree sum. , even.
Parity. Split into even-degree and odd-degree vertices. Even-degree sum is even; hence odd-degree sum is even. For the odd-degree sum to be even, the number of odd-degree vertices must be even.
Conclusion. Number of odd-degree vertices is even.