📂Graph Theory

Handshaking Lemma Proof

Theorem ¹

In any given graph, the sum of the degrees of all vertices is even.

Description

The term “handshake” obviously refers to the scenario where each vertex “shakes hands” with its adjacent vertices, and thus the total number of these handshakes corresponds to the sum of the degrees.

Proof

For a graph $G$, the sum of all degrees must exactly be twice the number of edges as per $$ \sum_{v \in V(G)} \deg (v) = 2 \left| E(G) \right| $$

■

Assuming that there exists an odd number of vertices with odd degrees, the sum of all vertices’ degrees would still be even, contradicting the handshake lemma. Thus, we derive the following corollary.

Corollary

In any graph, there must only be an even number of vertices with odd degrees.