Problem
COM-B1-M04-P006 Odd Degrees
#6
★★☆☆☆ Level 2 of 5
Prove that in every graph, the number of vertices of odd degree is even.
Use the sum of degrees.
The sum of degrees is \(2E\), hence even. The sum of degrees of even-degree vertices is even, so 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.
Classic double-counting lemma.