Exercise 239Combinatorics › Graph theoryHigh schoolAdded 3 Nov 2026

Parity of odd-degree vertices

#parity#degree#handshake

Statement

Show that the number of vertices of odd degree in any graph is even.

Hint

Use $\sum_v\deg(v)=2|E|$ and consider mod $2$ .

Show solutionHide solution

Mod 2. $\sum\deg(v)\equiv0\pmod2$ .

Split. Sum over even-degree vertices is even; so sum over odd-degree vertices is even. Sum of an even number of odd integers is even.

Conclusion. There is an even number of odd-degree vertices.