The handshaking lemma states that for a finite undirected graph 
with vertex set 
and edge set 
, the sum of the vertex degrees
is twice the number of edges,
 |
The name comes from interpreting the graph vertices as people and the graph edges as handshakes. Each handshake is counted once at each of its two participants, just as each edge contributes two to the degree sum. Since the right-hand side is even and each odd-degree vertex contributes an odd summand, the number of odd-degree vertices is even.
