The Handshaking Lemma
Table of Contents

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.

Screen%20Shot%202014-02-10%20at%206.33.21%20AM.png

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}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License