Handshake Lemma

Theorem

Let $G$ be a $\left({p, q}\right)$-graph, which may be a multigraph or a loop-graph, or both.

Let $V = \left\{{v_1, v_2, \ldots, v_p}\right\}$ be the vertex set of $G$.

Then:

$\displaystyle \sum_{i=1}^p \deg_G \left({v_i}\right) = 2 q$

where $\deg_G \left({v_i}\right)$ is the degree of vertex $v_i$.

That is, the sum of all the degrees of all the vertices of a graph is equal to twice the total number of its edges.

It follows directly that the number of odd vertices in $G$ must be even.

This result is known as the Handshake Lemma or Handshaking Lemma.

Direct Proof

In the notation $\left({p, q}\right)$-graph, $p$ is the number of vertices in $G$ (i.e. its order), and $q$ is the number of edges in $G$ , i.e. its size.

Each edge is incident to exactly two vertices.

The degree of each vertex is defined as the number of edges to which it is incident.

So when we add up the degrees of all the vertices, we are counting all the edges of the graph twice.

Now, consider the sum of the degrees of its vertices:

$\displaystyle K = \sum_{v \in V} \deg_G \left({v}\right)$.

From the above, we have that $K = 2 \left|{E}\right|$, which is an even integer.

Subtracting from $K$ the degrees of all vertices of even degree, we are left with the sum of all degrees of odd vertices in $V$.

That is:

$\displaystyle \left({\sum_{v \in V} \deg_G \left({v}\right)}\right) - \left({\sum_{v \in V : \deg_G \left({v}\right) = 2 k} \deg_G \left({v}\right)}\right) = \left({\sum_{v \in V : \deg_G \left({v}\right) = 2 k + 1} \deg_G \left({v}\right)}\right)$.

This must still be an even number, as it is equal to the difference of two even numbers.

Since this is a sum of exclusively odd terms, there must be an even number of such terms for the sum on the right side to be even.

Hence the result.

$\blacksquare$

Historical Note

This result was first given by Leonhard Euler in his 1736 paper Solutio problematis ad geometriam situs pertinentis, widely considered as the first ever paper in the field of graph theory.

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 2.1$: Theorems $2.1, \ 2.2$