The Handshaking Lemma

We will now look at a very important and well known lemma in graph theory.

Lemma 1 (The Handshaking Lemma): In any graph $G = (V(G), E(G))$, the sum of the degrees in the degree sequence of $G$ is equal to one half the number of edges in the graph, that is $\displaystyle{\sum_{v \in V(G)} \deg (v) = 2 \mid E(G) \mid}$.

• Proof: In any graph, each edge in $E(G)$ is attached to two vertices. Therefore each edge contributes $1$ to each of the two vertices it is connected to. Therefore $\sum_{v \in V(G)} \deg (v) = 2 \mid E(G) \mid$. $\blacksquare$

For example, let's look at the following graph where we label the degrees of each vertex in pink and each edge in blue.

Notice that the sum of the degrees in the degree sequence $(2 + 2 + 2 + 4 + 2 + 3 + 3)$ is $18$ and the number of edges is $9$. Hence we have verified that:

(1)

\begin{align} \quad \sum_{v \in V(G)} \deg (v) = 2 \mid E(G) \mid \quad 18 = 2(9) \\ \quad 18 = 18 \end{align}