The Handshake Lemma by Counting Incidences

Counting Edge Endpoints

The degree of a vertex counts how many edge ends meet there. This description suggests a way to find the sum of all vertex degrees: count all edge ends, first vertex by vertex and then edge by edge. Each edge has two ends, so the two counts must agree. Making this argument precise gives the handshake lemma.

Throughout, graphs are finite and undirected. A simple graph has no loops or multiple edges. When a multigraph is specified, parallel edges are distinct edges, and a loop has both of its ends at the same vertex. To count degrees consistently, distinguish the two endpoint occurrences of every edge. For a loop, these are two distinct occurrences even though they are attached to the same vertex.

Definition: An incidence is an occurrence of a vertex as an endpoint of an edge. For an edge $e$ with endpoints $u$ and $v$, its two endpoint occurrences give two incidences: one at $u$ and one at $v$. If $e$ is a loop at $u$, both incidences are at $u$. The degree $\deg(v)$ is the number of incidences at $v$.

In a simple graph, an edge $uv$ has one incidence at $u$ and one at $v$. In a multigraph, each parallel edge contributes its own incidences. A loop contributes two incidences at its vertex, not one. An isolated vertex has degree zero because no edge has an endpoint occurrence there.

For the proof, collect all incidences into a set $I(G)$. An element of $I(G)$ records both the edge and one of its two endpoint occurrences; recording the occurrence matters when the edge is a loop. Since the graph is finite, this is a finite set, and its size can be counted in two ways.

The Handshake Lemma

Lemma: In a finite undirected graph $G$, including a multigraph with loops, the number of incidences is $2|E(G)|$.

Proof. Fix an edge $e$. By the definition of an undirected edge, it has two endpoint occurrences. They give two elements of $I(G)$, even if both occurrences belong to the same vertex because $e$ is a loop. Every incidence belongs to one edge, so the incidence set is the disjoint union of the two-element sets belonging to the edges. Therefore $|I(G)|=2|E(G)|$. $\square$

Theorem (Handshake Lemma): For every finite undirected graph $G=(V,E)$, with loops counted twice in the degree of their vertex, $$ \sum_{v\in V}\deg(v)=2|E|. $$

Proof. Count the elements of $I(G)$ by their incident vertex. For each $v\in V$, exactly $\deg(v)$ incidences are at $v$, by the definition of degree. Every incidence is at exactly one vertex, including each of the two distinct incidences from a loop. Thus the sets of incidences at the vertices partition $I(G)$, and $$ |I(G)|=\sum_{v\in V}\deg(v). $$ By the lemma, $|I(G)|=2|E|$. Equating these two counts gives the stated identity. $\square$

The argument does not require the graph to be connected, to have any edges, or to have any vertices of positive degree. If $V$ is empty, then $E$ is empty and both sides are zero. If $V$ is nonempty but $E$ is empty, every vertex has degree zero, so again both sides are zero. Isolated vertices in a graph with edges simply add zero to the degree sum.

Worked Applications

Worked Example: A Simple Graph with an Isolated Vertex

Let $G=(V,E)$ be the simple graph with $V=\{a,b,c,d,e\}$ and $E=\{ab,ac,bc,cd\}$. Find every degree and verify the handshake lemma.

The edges incident with $a$ are $ab$ and $ac$, so $\deg(a)=2$. The edges incident with $b$ are $ab$ and $bc$, so $\deg(b)=2$. The edges incident with $c$ are $ac$, $bc$, and $cd$, so $\deg(c)=3$. The only edge incident with $d$ is $cd$, so $\deg(d)=1$. No edge is incident with $e$, so $\deg(e)=0$. Adding the degrees gives $2+2+3+1+0=8$. There are four listed edges, so twice the number of edges is $2\cdot4=8$.

Check: Count endpoint occurrences directly. The four edges $ab,ac,bc,cd$ each have two endpoint occurrences, giving $2+2+2+2=8$ incidences. This agrees with the degree sum, including the zero contribution from $e$.

Worked Example: Parallel Edges and a Loop

Let $G$ be a multigraph with $V=\{u,v,w\}$ and four distinct edges: $e_1$ and $e_2$ both have endpoints $u,v$; $e_3$ has endpoints $v,w$; and $e_4$ is a loop at $w$. Compute the degrees using endpoint occurrences and verify the lemma.

Each of $e_1$ and $e_2$ contributes one incidence at $u$ and one at $v$. Hence $\deg(u)=1+1=2$, and these two edges contribute $1+1$ to $\deg(v)$. The edge $e_3$ contributes one incidence at $v$ and one at $w$, so it raises both of those degrees by one. The loop $e_4$ contributes two incidences at $w$. Therefore $\deg(v)=1+1+1=3$ and $\deg(w)=1+2=3$. The total degree is $2+3+3=8$. There are four edges, so $2|E|=2\cdot4=8$.

Check: Count endpoint occurrences by edge: $e_1$ contributes two, $e_2$ contributes two, $e_3$ contributes two, and $e_4$ contributes two. The direct count is $2+2+2+2=8$, as required.

Worked Example: Two Components and an Isolated Vertex

Let $G$ be the simple graph with $V=\{1,2,3,4,5,6\}$ and $E=\{12,23,45\}$. Its components include the path on vertices $1,2,3$, the single edge $45$, and the isolated vertex $6$. Verify the degree sum without assuming the graph is connected.

Vertex $1$ is incident only with $12$, so $\deg(1)=1$. Vertex $2$ is incident with $12$ and $23$, so $\deg(2)=2$. Vertex $3$ is incident only with $23$, so $\deg(3)=1$. Each of vertices $4$ and $5$ is incident only with $45$, giving degrees $1$ and $1$. Vertex $6$ is isolated, so $\deg(6)=0$. The degree sum is $1+2+1+1+1+0=6$, while twice the edge count is $2\cdot3=6$.

Check: Count the endpoint occurrences in the three edges: $12$ has two, $23$ has two, and $45$ has two. Thus there are $2+2+2=6$ incidences. The components and isolated vertex do not change the count: every edge still contributes two incidences.

Why the Two Counts Must Agree

The proof is an instance of double counting. The objects being counted are not the vertices and not the edges alone, but the incidences that pair an edge with one of its endpoint occurrences. Grouping these objects by vertex gives the degree sum. Grouping them by edge gives two incidences per edge. The equality follows because both groups describe the same finite set.

This viewpoint also explains why the hypotheses matter. The result concerns undirected edges, each of which has two endpoint occurrences. A directed graph uses a different degree convention, separating in-degree and out-degree; those quantities should not be substituted into this statement without a separate argument. Likewise, a loop must be treated according to the stated convention. If a loop were counted only once in the degree, the degree would no longer count endpoint incidences.

The lemma is useful as a consistency check when degrees have been computed from a graph. If the sum of the degrees does not equal twice the number of edges, then at least one edge incidence has been omitted, counted more than once, or assigned to the wrong vertex. It is a check on the bookkeeping, not a substitute for identifying which individual degree is incorrect.

Common Mistake: Counting a Loop Once

In the multigraph example, a tempting but incorrect calculation is to assign the loop $e_4$ only one contribution at $w$. That gives the mistaken value $\deg(w)=1+1=2$: one incidence from $e_3$, plus one supposed contribution from $e_4$. The resulting degree sum would be $2+3+2=7$, while the four edges have $2\cdot4=8$ endpoint occurrences. The discrepancy signals the error.

Correct the calculation by distinguishing the loop's two endpoint occurrences. Both are at $w$, so $e_4$ contributes two, not one, and $\deg(w)=1+2=3$. The corrected degree sum is $2+3+3=8$, matching the incidence count. Parallel edges require the same care in a different way: each listed edge is counted separately, even when two edges have the same pair of endpoints.

Check Your Understanding

For each question, make the endpoint-occurrence convention explicit whenever a loop or a multigraph is involved.

Let $V=\{p,q,r\}$ and $E=\{pq,qr\}$. Find the three degrees and verify the handshake lemma.
A multigraph has vertices $x,y$, two distinct edges joining $x$ to $y$, and one loop at $x$. What are the degrees, and how many incidences are there?
Explain why an isolated vertex changes neither side of the handshake identity.
State the two different ways the proof counts the incidence set $I(G)$.
Give a concrete reason that counting a loop once in its vertex's degree would make the handshake lemma fail.