LemmaProved

Handshaking lemma

Statement

In any finite graph $G=(V,E)$ , $\sum_{v \in V} \deg(v) = 2|E|$ ; consequently, the number of vertices of odd degree is even.

Why is it true?

Every edge has exactly two endpoints, so when you add up the degree of every vertex, each edge gets counted twice — once from each end, like every handshake at a party being counted once by each participant. Since the total is twice an integer, it is even, which forces the number of odd-degree vertices to be even too.

Proof sketch

Each edge $\{u,v\}$ contributes exactly 1 to $\deg(u)$ and exactly 1 to $\deg(v)$ , so summing $\deg(v)$ over all vertices counts each edge exactly twice, giving $\sum_v \deg(v) = 2|E|$ . Since the right side is even, the sum of degrees is even; the sum of the even-degree vertices' degrees is automatically even, so the sum of the odd-degree vertices' degrees must also be even, which is only possible if there is an even number of them.

Stated by

stated 1736Leonhard Euler

Topics that use this theorem

Graphs, degree, and paths

Related theorems

Euler's theorem on Eulerian circuits

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Douglas B. West (2001). Introduction to Graph Theory