Problem
COM-B2-M01-P001 Number of Odd Degrees
#1
★★☆☆☆ Level 2 of 5
Prove that in every finite graph, the number of vertices of odd degree is even.
Count the sum of degrees in two ways.
Each edge contributes \(2\) to the degree sum, so the sum of degrees is \(2E\), even. The sum of even degrees is even, hence the sum of odd degrees is even. A sum of an odd number of odd integers would be odd, so the number of odd-degree vertices is even.
A classic entry point into incidence counting.