1
Every edge has two ends
So counting (vertex, incident edge) pairs by vertex gives the degree sum, and by edge gives 2|E|. That is the whole proof.
Lesson · Graphs and Trees · Basics
Degree and the Handshake Theorem
Each edge contributes 2 to the total degree, so Σ deg(v) = 2|E|. The immediate corollary — the number of odd-degree vertices is even — is used throughout the course.
deg(v) = number of edges at v
Σ_{v} deg(v) = 2|E| the handshake theorem
the number of ODD-degree vertices is EVEN
degree sequence: the degrees, sorted
One identity, one corollary
Core ideas
What this lesson establishes
The theorem is a double count and its corollary rules out whole families of graphs at a glance.
2
Odd degrees come in pairs
The total is even, so an odd number of odd degrees is impossible. This one line settles many existence questions.
3
The degree sequence is an invariant
Isomorphic graphs have the same sorted degrees, so different sequences prove non-isomorphism. Equal sequences prove nothing.
The material
Degrees
The definition, the theorem, and what it rules out.
Definition · Degree
The degree deg(v) of a vertex is the number of edges incident to it. A vertex of degree 0 is isolated; one of degree 1 is a leaf or pendant vertex.
Theorem · Handshake theorem
For any graph, Σ_{v ∈ V} deg(v) = 2|E|.
Count the incidences — pairs consisting of a vertex and an edge meeting it — in two ways.
By vertex: each v contributes deg(v) incidences, giving Σ deg(v).
By edge: each edge has exactly two ends, giving 2|E|.
One set counted twice, so the two expressions are equal.
□
This is a combinatorial proof in the sense of “Combinatorial Proof” in Combinatorics and Counting, and it is the cleanest example on the path: name the objects, count them two ways, conclude.
Theorem · The handshake corollary
In any graph, the number of vertices of odd degree is even.
Split the degree sum into even-degree and odd-degree vertices. The total is 2|E|, which is even, and the even-degree part is even, so the odd-degree part is even too.
A sum of odd numbers is even exactly when there are an even number of them.
□
Example · What the corollary rules out
There is no graph on 5 vertices in which every vertex has degree 3: that would be five odd degrees, an odd count. There is no party of 5 people where everyone shakes exactly 3 hands. The argument is one line and does not depend on the structure at all.
Definition · Degree sequence, regular graphs
The degree sequence is the list of degrees, usually sorted descending. A graph is k-regular if every vertex has degree k.
Theorem · Regular graphs
A k-regular graph on n vertices has nk/2 edges. It exists only if nk is even — so k-regular graphs on an odd number of vertices require k even.
Which sequences are realisable
Not every list of numbers is a degree sequence. (4, 3, 3, 2, 2) sums to 14, so |E| = 7, and it turns out to be realisable. (4, 4, 4, 4, 4) sums to 20 but requires each of five vertices to be adjacent to four others — that is K₅, which is fine. (5, 3, 3, 2, 1) is impossible in a simple graph on five vertices: a vertex cannot have degree 5 when only 4 others exist.
The Erdős–Gallai theorem gives a complete criterion, and the Havel–Hakimi algorithm constructs a graph when one exists. Both are beyond this course; the two necessary conditions above — even sum, and no degree exceeding n − 1 — catch most cases.
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Using degrees
Sum first; it is often the whole argument.
1
Compute the degree sum
It must be even, and it equals 2|E|. That is one edge count for free.
2
Count the odd degrees
If the count is odd, no such graph exists. This settles many existence questions before anything is drawn.
3
Check no degree exceeds n − 1
A vertex in a simple graph on n vertices has at most n − 1 neighbours.
4
Use the sequence as an invariant
Different sorted sequences prove two graphs non-isomorphic. Equal sequences prove nothing, as “Subgraphs and Graph Isomorphism” shows.
Degrees
Score 0 / 0Choose the answer you can justify.
Three existence questions
All three are settled by counting degrees.
1. A graph on 7 vertices, every degree 3?
seven odd degrees — an ODD count. IMPOSSIBLE
2. A graph on 8 vertices, every degree 3?
eight odd degrees — even. Σ deg = 24, so |E| = 12.
The cube graph Q₃ is one. POSSIBLE
3. A graph on 6 vertices with degrees 5,5,5,5,5,5?
Σ = 30, |E| = 15 = C(6,2). That is K₆. POSSIBLE
4. Degrees 5,3,3,2,1 on 5 vertices?
Σ = 14 is even, but degree 5 needs 5 neighbours
and only 4 other vertices exist. IMPOSSIBLE
Case 4 shows the parity test alone is not sufficient. Two necessary conditions — even sum and no degree above n − 1 — catch most impossible sequences, and the full criterion is the Erdős–Gallai theorem.
Common mistakes
1
Forgetting that Σ deg = 2|E|, not |E|Every edge is counted at both ends. Halving is the step that is skipped.
2
Assuming any sequence with an even sum is realisable(5,3,3,2,1) has an even sum and is impossible on five vertices. The maximum-degree condition is separate.
3
Using equal degree sequences as proof of isomorphismThey are necessary and not sufficient. “Subgraphs and Graph Isomorphism” gives two non-isomorphic graphs with identical sequences.
Check your understanding
✓
Finish when you check parity before attempting a construction.
Decide whether a graph exists with degree sequence (4,4,3,3,2,2), and say which test settles it. The sum is 18, so |E| = 9, and no degree exceeds 5 — so try to build one.
Note: The handshake theorem is the most reused fact in this course. It supplies the edge count in “Trees”'s tree characterisation, the parity condition in “Euler and Hamilton Paths”'s Euler criterion, and the counting argument in “Planar Graphs and Euler's Formula”'s planarity bound.