Handshaking lemma
Relate all vertex degrees to the number of edges in an undirected graph.
Handshaking lemma is one of 4 graphs formulas in the discrete math section of this library, and it is used at university level.
Why handshaking lemma works
Every edge has two ends, and each end contributes 1 to the degree of the vertex it touches. So walking around the graph and adding up all the degrees counts each edge once from each side. That total has to be twice the number of edges, no matter how the graph is shaped.
What each symbol means
$V$ is vertex set and $E$ edge set.
Handshaking lemma: when it holds
Each undirected edge contributes two degree incidences; loops require the usual degree-two convention.
When it stops applying
It is a statement about undirected graphs. In a directed graph each arrow adds 1 to one vertex's out-degree and 1 to another's in-degree, so you count those two totals separately and each equals the number of arrows on its own.
Handshaking lemma: a worked example
A graph with $7$ edges has total degree $14$.
The mistake to avoid
What people do: Students treat the total degree as the number of edges and forget to halve it.
Why it goes wrong: Each edge was counted from both ends, so the total degree always overstates the edge count by a factor of exactly two.
Do this instead: Divide the degree total by 2. If six people each shake hands with three others, the degrees add to 18, so there were 9 handshakes, not 18.
Handshaking lemma: step by step
- Name the unknown, and the unit the answer has to come out in.
- Match the symbols to your values. $V$ is vertex set and $E$ edge set.
- Check the conditions before substituting. Each undirected edge contributes two degree incidences; loops require the usual degree-two convention.
- Substitute, keep exact values to the last line, then test the sign, size, and unit against a rough estimate — the check that catches most discrete math slips.
Where this formula fits
- Subject
- Discrete Math formulas — 11 entries in this library
- Topic
- Graphs
- Level
- University
Formulas are easiest to keep when they sit inside a method rather than on a list. Use the links below to see where handshaking lemma comes from, to check a calculation against a tool, and to practise it until you can recall it without looking.
- Discrete Math Calculator — check your substitution and the value it produces.
- Study discrete math — the subject guide that explains the ideas these formulas compress.
- Discrete Math Practice — questions that make you retrieve the formula instead of recognising it.
- All 11 discrete math formulas — the full grouped reference, or the complete formula library.
Questions about handshaking lemma
Can a graph have exactly three vertices of odd degree?
No. The degree total must be even, and odd degrees can only pair up to an even total in even numbers, so the count of odd-degree vertices is always even. This is the lemma's most useful corollary.
How does a loop count toward degree?
It counts 2, because both of its ends attach to the same vertex. That convention exists precisely so the lemma keeps working when loops are allowed.
Why is it called the handshaking lemma?
Picture people as vertices and handshakes as edges. Adding up how many hands each person shook double counts every handshake, since two people take part in each one.
What is the total degree of a graph with 7 edges?
Exactly 14, whatever the shape. That works in reverse too: if the degrees you listed add to an odd number, you have miscounted somewhere.