Exercise 880Combinatorics › Counting principlesL1Added 3 Nov 2026

Degrees in a graph

#graph degree#handshake lemma#parity

Statement

In a graph with $n$ vertices and $m$ edges, show that $\sum_v\deg(v)=2m$ .

Hint

Double count pairs (vertex, incident edge).

Show solutionHide solution

Count pairs. $\{(v,e):v\text{ incident to }e\}$ .

By vertex. $\sum_v\deg(v)$ .

By edge. Each edge has $2$ endpoints: $2m$ .

Conclusion. $\sum_v\deg(v)=2m$ .

Corollary. The sum of degrees is always even.