# Handshake Lemma

## Contents

## Theorem

Let $G$ be a $\tuple {p, q}$-undirected graph, which may be a multigraph or a loop-graph, or both.

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

Then:

- $\displaystyle \sum_{i \mathop = 1}^p \map {\deg_G} {v_i} = 2 q$

where $\map {\deg_G} {v_i}$ is the degree of vertex $v_i$.

That is, the sum of all the degrees of all the vertices of an graph is equal to twice its size.

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

### Corollary

The number of odd vertices in $G$ is even.

## Proof

In the notation $\tuple {p, q}$-graph, $p$ is its order and $q$ its size.

That is, $p$ is the number of vertices in $G$, and $q$ is the number of edges in $G$.

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.

$\blacksquare$

## Examples

### Arbitrary Order $8$ Graph

The above simple graph has $8$ vertices and $10$ edges (which can be ascertained by counting).

\(\displaystyle \map \deg {v_1}\) | \(=\) | \(\displaystyle 2\) | |||||||||||

\(\displaystyle \map \deg {v_2}\) | \(=\) | \(\displaystyle 3\) | |||||||||||

\(\displaystyle \map \deg {v_3}\) | \(=\) | \(\displaystyle 3\) | |||||||||||

\(\displaystyle \map \deg {v_4}\) | \(=\) | \(\displaystyle 3\) | |||||||||||

\(\displaystyle \map \deg {v_5}\) | \(=\) | \(\displaystyle 4\) | |||||||||||

\(\displaystyle \map \deg {v_6}\) | \(=\) | \(\displaystyle 1\) | |||||||||||

\(\displaystyle \map \deg {v_7}\) | \(=\) | \(\displaystyle 2\) | |||||||||||

\(\displaystyle \map \deg {v_8}\) | \(=\) | \(\displaystyle 2\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \sum \map \deg V\) | \(=\) | \(\displaystyle 2 + 3 + 3 + 3 + 4 + 1 + 2 + 2\) | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle 20\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle 2 \times 10\) |

### Impossible Order $6$ Graph

There exists no undirected graph whose vertices have degrees $2, 3, 3, 4, 4, 5$.

### No Graph with One Odd Vertex

There exists no undirected graph with exactly one odd vertex.

## Historical Note

The **Handshake Lemma** was first given by Leonhard Euler in his $1736$ paper *Solutio problematis ad geometriam situs pertinentis*.

This is widely considered as the first ever paper in the field of graph theory.

## Sources

- 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.1$: The Degree of a Vertex: Theorem $2.1$