[T] Handshake Lemma (T1.1)

October, 2026

For any graph $G$ , the sum of the degrees of its vertices is twice the number of its edges:

v \in V \sum d (v) = 2 m

where $d (v)$ is the degree of vertex $v$ : the number of edges incident with $v$ , each loop counting as two edges.

The name comes from the picture of people at a party shaking hands: every handshake involves exactly two hands, so the total number of hands shaken is twice the number of handshakes.

Proof

Uses counting in two ways on the incidence matrix $M$ of $G$ , the $n \times m$ matrix where $m_{v e}$ is the number of times (0, 1 or 2) that vertex $v$ and edge $e$ are incident.

Row sums: the row of vertex $v$ sums to exactly $d (v)$ , so the sum of all entries of $M$ is $\sum_{v \in V} d (v)$ .
Column sums: every edge has two ends, so each of the $m$ columns sums to $2$ , and the sum of all entries of $M$ is $2 m$ .

Equating the two:

v \in V \sum d (v) = v \in V \sum e \in E \sum m_{v e} = e \in E \sum v \in V \sum m_{v e} = e \in E \sum 2 = 2 m

Example

A graph with $n = 5$ vertices and $m = 6$ edges, where $e_{6}$ is a loop at $v_{5}$ (shown in red):

Its incidence matrix, with the row sums on the right and the column sums along the bottom:

v_{1} v_{2} v_{3} v_{4} v_{5} column sum e_{1} 110002 e_{2} 101002 e_{3} 011002 e_{4} 001102 e_{5} 000112 e_{6} 000022 row sum = d (v) 2232 3 \leftarrow loop counts twice \sum_{v} d (v) = 12 = 2 \cdot 6 = 2 m

Each row sums to the degree of its vertex: $2 + 2 + 3 + 2 + 3 = 12$ .
Each column sums to $2$ , because every edge has two ends: $6 \cdot 2 = 12$ .
The loop: $e_{6}$ has both ends at $v_{5}$ , so its whole column sum of $2$ sits in one cell ( $m_{v_{5} e_{6}} = 2$ ). This is why a loop adds $2$ to the degree; otherwise the identity would fail.

[C] Number of odd-degree vertices is even (C1.2)

In any graph, the number of vertices of odd degree is even.

Proof

Consider the handshake identity modulo 2. Each term satisfies

d (v) \equiv {1 (mod 2) 0 (mod 2) if d (v) is odd if d (v) is even

So modulo 2 the left-hand side is congruent to the number of odd-degree vertices, while the right-hand side $2 m \equiv 0$ . Hence the number of odd-degree vertices is $\equiv 0 (mod 2)$ , i.e. even.

In the example above, the odd-degree vertices are $v_{3}$ and $v_{5}$ (both have degree $3$ ). That is $2$ of them, an even number.

Consequences

The average degree $\overset{ˉ}{d} (G) = \frac{1}{n} \sum_{v \in V} d (v) = \frac{2 m}{n}$ .
A $k$ -regular graph on $n$ vertices has $m = \frac{nk}{2}$ edges, so $nk$ must be even (e.g. there is no 3-regular graph on an odd number of vertices).