The handshaking lemma

Theorem

The handshaking lemma

T-030Home MU-105Threads structure · number

Statement

Let \( G = (V, E) \) be a finite undirected multigraph: \( V \) is a finite set of vertices, \( E \) a finite multiset of edges, where each edge is assigned an unordered pair of (not necessarily distinct) endpoints in \( V \), and a loop at \( v \) contributes \( 2 \) to the degree of \( v \). Write \( \deg(v) \) for the degree of \( v \), i.e. the number of edge-endpoints incident with \( v \), counted with multiplicity. Then \[ \sum_{v \in V} \deg(v) \;=\; 2\,|E| . \] In particular the left-hand side is always an even natural number.

Why it matters

This is, historically and pedagogically, the first theorem of graph theory: it appears implicitly in Euler's 1736 analysis of the Königsberg bridges. It is the prototype of a double-counting argument — count one finite set (vertex–edge incidences) in two different ways and equate the answers. Almost every counting identity in combinatorics is proved by some elaboration of this move.

Its parity consequence — the number of odd-degree vertices in any finite graph is even — powers a remarkable range of existence and impossibility proofs: Euler's characterisation of Eulerian circuits, edge counts of regular graphs, non-existence of certain configurations, and (much later) the definition of the complexity class \( \mathsf{PPA} \).

Hypotheses

Hypothesis.\( V \) and \( E \) are finite. On the infinite ray \( \mathbb{N} \) with edges \( \{n, n+1\} \), both \( \sum_v \deg(v) \) and \( 2|E| \) are infinite, so the identity degenerates; worse, one can build infinite graphs with exactly one vertex of odd degree (e.g. a ray: the origin has degree \( 1 \), every other vertex degree \( 2 \)), so the parity corollary is outright false for infinite graphs.

Hypothesis.The graph is undirected. For a directed graph the correct identity splits: \( \sum_v \deg^{+}(v) = \sum_v \deg^{-}(v) = |E| \), not \( 2|E| \). The single arc \( u \to v \) has out-degree sum \( 1 \), which is odd.

Hypothesis.Loops count twice in the degree. Under the (nonstandard) convention that a loop contributes \( 1 \), the graph consisting of one vertex with one loop gives \( \sum_v \deg(v) = 1 \neq 2 = 2|E| \). The convention is not arbitrary: it is forced by the topological picture of an edge as having two end-segments, and by the incidence-matrix formulation in which each column must sum to \( 2 \).

Proof

We double-count vertex–edge incidences. To be honest about loops and parallel edges we work with the incidence multiplicity function rather than with the naive relation "\( v \in e \)".

Formally, a finite multigraph is a triple \( (V, E, \varphi) \) with \( V, E \) finite sets and \( \varphi : E \to \binom{V}{2} \cup \binom{V}{1} \) assigning to each edge its set of endpoints (a \( 1 \)-element set for a loop). Define the incidence multiplicity \( \iota : V \times E \to \{0, 1, 2\} \) by: \( \iota(v,e) = 2 \) if \( e \) is a loop at \( v \); \( \iota(v,e) = 1 \) if \( v \in \varphi(e) \) and \( e \) is not a loop; \( \iota(v,e) = 0 \) otherwise.

Fixing a precise model; this is the standard endpoint-function formalisation of multigraphs, and \( \iota \) encodes "how many end-segments of \( e \) attach to \( v \)". A

\[ \deg(v) \;=\; \sum_{e \in E} \iota(v, e) \qquad \text{for every } v \in V. \]

This is the definition of degree in a multigraph: the number of edge-end-segments at \( v \), a loop contributing \( 2 \). The sum is a finite sum of natural numbers since \( E \) is finite. A

\[ \sum_{v \in V} \iota(v, e) \;=\; 2 \qquad \text{for every } e \in E. \]

Key observation. Fix \( e \). If \( e \) is a loop at \( w \), the sum has exactly one nonzero term, \( \iota(w,e) = 2 \). If \( e \) has two distinct endpoints \( u \neq w \), the sum has exactly two nonzero terms, \( \iota(u,e) = \iota(w,e) = 1 \). In both cases the total is \( 2 \): every edge has exactly two end-segments. B

\[ \sum_{v \in V} \sum_{e \in E} \iota(v, e) \;=\; \sum_{e \in E} \sum_{v \in V} \iota(v, e). \]

Exchange of two finite sums (finite Fubini). Legality: both sides equal \( \sum_{(v,e) \in V \times E} \iota(v,e) \), a sum over the finite set \( V \times E \), and a finite sum of natural numbers is invariant under any rearrangement by associativity and commutativity of \( + \) in \( \mathbb{N} \) (proved by induction on \( |V \times E| \)). This is the step that genuinely uses finiteness of both \( V \) and \( E \). C

\[ \sum_{v \in V} \deg(v) \;\overset{(2)}{=}\; \sum_{v \in V} \sum_{e \in E} \iota(v,e) \;\overset{(4)}{=}\; \sum_{e \in E} \sum_{v \in V} \iota(v,e) \;\overset{(3)}{=}\; \sum_{e \in E} 2 \;=\; 2\,|E|. \]

Chain the previous three steps; the final equality is the definition of cardinality: summing the constant \( 2 \) over the finite set \( E \) gives \( 2|E| \). A

Corollary (parity form): the number of vertices of odd degree is even.

Reduce the identity modulo \( 2 \): \( \sum_{v} \deg(v) \equiv 0 \pmod 2 \), and the even-degree vertices contribute \( 0 \) to the sum mod \( 2 \), so the number of odd-degree summands must be even. Uses only that \( \mathbb{Z}/2\mathbb{Z} \) is a ring and reduction mod \( 2 \) is a homomorphism. B

Result

\[ G = (V,E) \text{ a finite multigraph} \;\Longrightarrow\; \sum_{v \in V} \deg(v) = 2\,|E| \]

Reading. Every edge has two ends, and the total degree simply counts edge-ends. So the degree sum is exactly twice the edge count — and in particular it is always even: at any finite party, the number of hands shaken, totalled over all guests, is twice the number of handshakes, and the number of guests who shook an odd number of hands is even.

Scope. Holds for every finite undirected graph — simple or not, connected or not, with loops (counted twice) and parallel edges allowed, including the empty graph. It fails or degenerates for infinite graphs, and takes the different form \( \sum_v \deg^{+}(v) = \sum_v \deg^{-}(v) = |E| \) for digraphs.

Corollaries & converses

Parity corollary. In any finite graph the number of vertices of odd degree is even (Step 6). This weaker statement is itself often called "the handshaking lemma".
Regular graphs. If \( G \) is \( k \)-regular on \( n \) vertices then \( |E| = kn/2 \); hence a \( k \)-regular graph with \( k \) odd must have an even number of vertices.
Complete graphs. \( |E(K_n)| = \binom{n}{2} \), since \( \sum_v \deg(v) = n(n-1) \).
Trees. Combined with \( |E| = n - 1 \) (cited: standard tree theorem), degree-sum arguments control leaf counts; e.g. every finite tree with \( n \geq 2 \) vertices has at least two leaves, since \( \sum_v \deg(v) = 2n - 2 \lt 2n \) forbids all degrees being \( \geq 2 \) except at most one.
Converse (multigraph version): TRUE. Every sequence \( d_1, \dots, d_n \) of non-negative integers with \( \sum_i d_i \) even is the degree sequence of some multigraph with loops: pair up the odd-degree indices with edges, then add loops (each worth \( 2 \)) to make up the remaining degree.
Converse (simple-graph version): FALSE. Even degree sum does not guarantee a simple realisation: \( (4, 1, 1) \) has even sum \( 6 \), but a simple graph on \( 3 \) vertices has maximum possible degree \( 2 \). The correct characterisation is the Erdős–Gallai theorem (cited, not proved here).

Fails without

Drop finiteness. The one-way infinite ray \( 0 - 1 - 2 - 3 - \cdots \) has exactly one vertex of odd degree (the origin, degree \( 1 \)), so the parity corollary fails; the identity itself becomes \( \infty = \infty \), carrying no information. Even for locally finite infinite graphs no meaningful version of the equation survives without extra structure (e.g. finite edge cuts).
Drop undirectedness (read degrees as out-degrees). The digraph with vertices \( \{u, v\} \) and single arc \( u \to v \) has \( \sum_x \deg^{+}(x) = 1 \neq 2 = 2|E| \). The correct directed statement is \( \sum_x \deg^{+}(x) = \sum_x \deg^{-}(x) = |E| \).
Drop the loops-count-twice convention. One vertex, one loop, loop counted once: degree sum \( 1 \), edge count \( 1 \), and \( 1 \neq 2 \) — the theorem is false and, worse, a graph now "exists" with odd degree sum, destroying every parity argument downstream.

Common errors

Loop miscounting. Counting a loop as contributing \( 1 \) to the degree. A loop occupies both end-slots of its edge, so it contributes \( 2 \); otherwise the lemma itself breaks (see "Fails without").
Digraph transfer. Applying \( \sum \deg = 2|E| \) to out-degrees or in-degrees of a directed graph. Each arc has one tail and one head, so out-degree and in-degree sums each equal \( |E| \), not \( 2|E| \).
Illicit converse. Concluding that any sequence with even sum is the degree sequence of a simple graph. False: \( (4,1,1) \). Even sum is necessary, not sufficient (Erdős–Gallai gives the full condition).
Parity overreach. Sliding from "the degree sum is even" to "every degree is even" or "the number of edges is even". Neither follows: the path \( P_3 \) has degrees \( 1, 2, 1 \) and \( |E| = 2 \); the triangle has \( |E| = 3 \), odd.
Halving too early. Computing \( |E| = \frac{1}{2}\sum_v \deg(v) \) but forgetting to check the sum is even — an odd total is not a rounding issue, it is a proof that the proposed graph does not exist.
Name confusion. Using "handshaking lemma" for the parity corollary and then citing it as if it were the full identity (or vice versa) mid-proof. State which form you are invoking.

Discussion

The result descends from Euler's 1736 paper Solutio problematis ad geometriam situs pertinentis on the seven bridges of Königsberg — generally taken as the founding document of graph theory. Euler observed that in any walk crossing each bridge exactly once, every intermediate land mass must be entered as often as it is left, which forces parity conditions on the degrees; the degree-sum identity is the bookkeeping fact underneath. The modern statement and its role as "Theorem 1" of every graph theory course crystallised in the twentieth century.

Structurally, the proof is the simplest instance of double counting: build the incidence set \( I = \{(v, e) : v \text{ an end of } e\} \) (with multiplicity), and evaluate \( |I| \) by rows and by columns. In linear-algebraic language, let \( B \in \mathbb{Z}^{V \times E} \) be the (unsigned) incidence matrix, with \( B_{v,e} = \iota(v,e) \). Row sums of \( B \) are the degrees; column sums are all \( 2 \); the lemma says the grand total of \( B \) can be computed either way. This viewpoint scales up: the same matrix, signed, has rank \( |V| - c(G) \) over \( \mathbb{R} \) and underlies the graph Laplacian \( L = D - A \), whose trace identity \( \operatorname{tr}(L) = \sum_v \deg(v) = 2|E| \) is the handshaking lemma read spectrally: the sum of Laplacian eigenvalues of a finite graph is \( 2|E| \).

The parity corollary is a workhorse far beyond graph theory. Euler's theorem (a connected finite multigraph has a closed Eulerian trail iff every degree is even) uses it; so do "degree arguments" in combinatorial topology — Sperner's lemma is standardly proved by building an auxiliary graph in which fully-labelled simplices are precisely the odd-degree vertices, then invoking the corollary to conclude their number is odd overall, hence nonzero. The same pattern proves Smith's theorem on Hamiltonian cycles in cubic graphs: every edge of a \( 3 \)-regular graph lies on an even number of Hamiltonian cycles.

In computational complexity the corollary has been elevated to a definition. Papadimitriou's class \( \mathsf{PPA} \) ("Polynomial Parity Argument") consists of the total search problems reducible to Leaf: given a graph of maximum degree \( 2 \) described implicitly by a polynomial-size circuit, and one vertex of degree \( 1 \), find another odd-degree vertex. The handshaking corollary guarantees a solution exists, but the proof is non-constructive in the implicit-graph setting: it counts, it does not locate. \( \mathsf{PPA} \)-completeness of problems such as Consensus-Halving (Filos-Ratsikas–Goldberg, 2018) measures precisely the computational cost hidden inside this one-line parity argument. A related lesson concerns infinite combinatorics: the lemma is irreducibly a theorem about finite sums, and its failure on the infinite ray is a standard first example of how compactness-free infinite arguments break.

Common misconceptions. (i) "The handshaking lemma" names two statements — the identity \( \sum \deg = 2|E| \) and its parity corollary; authors differ, so check which is meant. (ii) The lemma does not say the number of edges is even, nor that any individual degree is even. (iii) It is not restricted to simple graphs: it holds verbatim for multigraphs, provided loops count twice — indeed the multigraph version is the natural one.

Worked examples

Example 1. No \( 5 \)-regular graph on \( 9 \) vertices exists.

Suppose, for contradiction, that \( G \) is a simple graph with \( |V| = 9 \) and \( \deg(v) = 5 \) for every \( v \in V \).

Set-up for proof by contradiction; "\( 5 \)-regular" unpacked into its definition. A

\[ \sum_{v \in V} \deg(v) = 9 \times 5 = 45. \]

Sum of a constant over a \( 9 \)-element set. A

\[ 45 = 2\,|E| \quad\Longrightarrow\quad |E| = \tfrac{45}{2} \notin \mathbb{N}. \]

Handshaking lemma applied to \( G \); but \( |E| \) is the cardinality of a finite set, hence a natural number, and \( 45 \) is odd — contradiction. B

\[ \text{No graph on } 9 \text{ vertices is } 5\text{-regular.} \]

Reading. More generally, a \( k \)-regular graph with \( k \) odd must have evenly many vertices: \( kn = 2|E| \) forces \( n \) even. Nine people cannot each shake hands with exactly five of the others.

Scope. Pure parity; needs no structure beyond finiteness, so it rules out multigraph realisations too (with loops counted twice).

Example 2. Edge count of the hypercube graph \( Q_n \).

The hypercube \( Q_n \) has vertex set \( \{0,1\}^n \), with \( u \sim v \) iff \( u \) and \( v \) differ in exactly one coordinate. So \( |V(Q_n)| = 2^n \).

Definition of \( Q_n \); \( |\{0,1\}^n| = 2^n \) by the product rule. A

\[ \deg(v) = n \qquad \text{for every } v \in V(Q_n). \]

From any word \( v \in \{0,1\}^n \) there are exactly \( n \) coordinates available to flip, each giving a distinct neighbour; so \( Q_n \) is \( n \)-regular. B

\[ 2\,|E(Q_n)| = \sum_{v} \deg(v) = n \cdot 2^n \quad\Longrightarrow\quad |E(Q_n)| = n \, 2^{n-1}. \]

Handshaking lemma, then divide by \( 2 \) — legal in \( \mathbb{N} \) here because \( n\,2^n \) is even for \( n \geq 1 \) (and the \( n = 0 \) case reads \( 0 = 0 \)). A

\[ |E(Q_n)| = n\,2^{n-1} \]

Reading. Counting edges directly by listing would be painful; regularity plus handshaking turns it into one multiplication. Check: \( Q_2 \) is a \( 4 \)-cycle, and \( 2 \cdot 2^1 = 4 \). \( Q_3 \) is the cube, \( 3 \cdot 2^2 = 12 \) edges.

Scope. The same template \( |E| = kn/2 \) computes the edge count of any \( k \)-regular graph: Petersen (\( 3 \)-regular, \( 10 \) vertices, \( 15 \) edges), \( K_n \) (\( (n-1) \)-regular, \( \binom{n}{2} \) edges).

Problems

Using the handshaking lemma, compute the number of edges of the complete graph \( K_n \) and of the complete bipartite graph \( K_{m,n} \).
Solution

In \( K_n \) every vertex is adjacent to the other \( n - 1 \) vertices, so \( K_n \) is \( (n-1) \)-regular. By handshaking, \( 2|E| = n(n-1) \), so \( |E(K_n)| = \frac{n(n-1)}{2} = \binom{n}{2} \). (The division is legal: \( n(n-1) \) is a product of consecutive integers, hence even.)

In \( K_{m,n} \) with parts \( A \) (\( |A| = m \)) and \( B \) (\( |B| = n \)): each vertex of \( A \) has degree \( n \) and each vertex of \( B \) has degree \( m \). So \( 2|E| = \sum_{v} \deg(v) = mn + nm = 2mn \), giving \( |E(K_{m,n})| = mn \).
At a conference, some pairs of participants shake hands. Prove that at every moment, the number of participants who have shaken an odd number of hands is even. Deduce that \( 7 \) people cannot each shake hands with exactly \( 3 \) of the others.
Solution

Model the situation as a finite graph \( G \): vertices are participants, edges are handshakes that have occurred (a multigraph if repeat handshakes are allowed — the argument is unaffected). The number of hands person \( v \) has shaken is \( \deg(v) \). By the handshaking lemma \( \sum_v \deg(v) = 2|E| \equiv 0 \pmod 2 \). Splitting the sum over even-degree and odd-degree vertices, the even-degree part is \( \equiv 0 \pmod 2 \), so the odd-degree part must be too: \( \sum_{v \,:\, \deg(v) \text{ odd}} \deg(v) \equiv 0 \pmod 2 \). A sum of \( t \) odd numbers is congruent to \( t \pmod 2 \), so \( t \), the number of odd-degree vertices, is even.

If \( 7 \) people each shook exactly \( 3 \) hands, there would be \( 7 \) vertices of odd degree — an odd number of odd-degree vertices, contradicting the above. (Equivalently: \( \sum \deg = 21 \) is odd, so it cannot equal \( 2|E| \).)
Let \( T \) be a finite tree in which every non-leaf vertex has degree exactly \( 3 \). Prove that if \( T \) has \( L \) leaves (\( L \geq 2 \)) then it has exactly \( L - 2 \) internal vertices, hence \( 2L - 2 \) vertices in total. You may cite that a tree on \( n \) vertices has \( n - 1 \) edges.
Solution

Let \( i \) be the number of internal (degree-\( 3 \)) vertices, so \( n = L + i \) and, by the cited tree theorem, \( |E| = n - 1 = L + i - 1 \). Compute the degree sum two ways. Directly: leaves contribute \( 1 \) each and internal vertices \( 3 \) each, so \( \sum_v \deg(v) = L + 3i \). By handshaking: \( \sum_v \deg(v) = 2|E| = 2(L + i - 1) \).

Equate: \( L + 3i = 2L + 2i - 2 \), so \( i = L - 2 \). Total vertex count: \( n = L + (L - 2) = 2L - 2 \). (Consistency check: \( L = 2 \) gives \( i = 0 \), the path \( P_2 \) — but note every internal vertex of a longer path has degree \( 2 \), so \( P_k \) with \( k \geq 3 \) is correctly excluded by the hypothesis.)
(Directed version.) Let \( D = (V, A) \) be a finite directed multigraph. Prove that \( \sum_{v \in V} \deg^{+}(v) = \sum_{v \in V} \deg^{-}(v) = |A| \), and explain precisely how this implies the handshaking lemma for the underlying undirected multigraph obtained by forgetting orientations.
Solution

Define \( \tau(v, a) = 1 \) if \( v \) is the tail of arc \( a \), else \( 0 \); and \( \eta(v,a) = 1 \) if \( v \) is the head of \( a \), else \( 0 \) (for a directed loop at \( v \), both \( \tau(v,a) = 1 \) and \( \eta(v,a) = 1 \)). Then \( \deg^{+}(v) = \sum_{a} \tau(v,a) \) and, for each fixed arc \( a \), \( \sum_v \tau(v,a) = 1 \) (every arc has exactly one tail). Exchanging the two finite sums (finite Fubini, as in the main proof): \( \sum_v \deg^{+}(v) = \sum_a \sum_v \tau(v,a) = \sum_a 1 = |A| \). The identical argument with \( \eta \) gives \( \sum_v \deg^{-}(v) = |A| \).

Now orient each edge of an undirected multigraph \( G \) arbitrarily (choose a tail and head for each edge; for a loop both are its unique endpoint) to obtain a digraph \( D \) with \( |A| = |E| \). Forgetting orientation, \( \deg_G(v) = \deg^{+}_D(v) + \deg^{-}_D(v) \): every end-segment of an edge at \( v \) is either a tail-end or a head-end, and a loop at \( v \) contributes one of each — total \( 2 \), matching the loops-count-twice convention. Summing over \( v \): \( \sum_v \deg_G(v) = \sum_v \deg^{+}(v) + \sum_v \deg^{-}(v) = |A| + |A| = 2|E| \). This re-derives the handshaking lemma and explains the factor \( 2 \): it is "one tail plus one head per edge".
(Face handshaking and planarity.) Let \( G \) be a connected simple planar graph with \( n \geq 3 \) vertices, drawn in the plane, and for a face \( f \) let \( \deg(f) \) be the number of edge-sides on its boundary walk. (a) Prove \( \sum_{f} \deg(f) = 2|E| \), the sum over all faces of the drawing. (b) Using Euler's formula \( n - |E| + |F| = 2 \) (cited), deduce \( |E| \leq 3n - 6 \), and conclude that \( K_5 \) is not planar.
Solution

(a) Double-count incidences between edges and face-sides. Every edge of a plane drawing has exactly two sides, and each side lies on the boundary walk of exactly one face (the two sides may border the same face — e.g. a bridge — in which case that edge contributes \( 2 \) to that single face's degree, exactly as a loop does to a vertex degree). Define \( \kappa(f, e) \in \{0,1,2\} \) as the number of sides of \( e \) bordering \( f \); then \( \deg(f) = \sum_e \kappa(f,e) \) by definition, and \( \sum_f \kappa(f,e) = 2 \) for each edge \( e \). Exchanging the finite sums gives \( \sum_f \deg(f) = \sum_e 2 = 2|E| \). This is the handshaking argument verbatim with "faces" in place of "vertices".

(b) \( G \) is simple with \( n \geq 3 \), so every face of any drawing has boundary walk of length at least \( 3 \) (no faces bounded by \( 1 \) edge since no loops, none by \( 2 \) since no parallel edges; and if \( |E| \leq 1 \) the bound \( |E| \leq 3n - 6 \) holds trivially for \( n \geq 3 \), so assume \( |E| \geq 2 \), where the boundary walk of every face has length \( \geq 3 \)). Then \( 2|E| = \sum_f \deg(f) \geq 3|F| \), so \( |F| \leq \frac{2}{3}|E| \). Substituting into Euler's formula: \( 2 = n - |E| + |F| \leq n - |E| + \tfrac{2}{3}|E| = n - \tfrac{1}{3}|E| \), hence \( |E| \leq 3n - 6 \).

For \( K_5 \): \( n = 5 \), \( |E| = \binom{5}{2} = 10 \), but \( 3n - 6 = 9 \lt 10 \). So \( K_5 \) admits no planar drawing.