Degree of a Vertex and Handshaking Lemma: Notes and FAQs

The degree of a vertex is the number of edges touching it — the simplest and most useful measurement in graph theory. If a city has five roads leaving it, its vertex has degree 5. The handshaking lemma is the famous rule that connects all these degrees: add up the degrees of every vertex in a graph, and the total is always exactly twice the number of edges.

This matters because the lemma is a built-in error checker. If you count degrees in a network diagram and the sum is odd, you made a mistake — the sum can never be odd. It also proves surprising facts, like why the number of people who have shaken an odd number of hands is always even.

Key Concepts

• Degree of a vertex v, written deg(v): the count of edges incident on v. A loop contributes 2, because both its ends touch the vertex.
• Isolated vertex: degree 0. Pendant vertex: degree 1, at the end of a single edge.
• Odd and even vertices: a vertex is odd if its degree is odd, even if its degree is even.
• Handshaking lemma: for any graph with m edges, the degrees sum to 2m.
• Corollary: every graph has an even number of odd-degree vertices.

Formulas

Sum of degrees = 2m, where m is the number of edges.

Why it works: every edge has two ends, so each edge contributes 1 to the degree of each endpoint — 2 per edge in total. A loop's two ends both land on the same vertex, which is why a loop adds 2 and keeps the formula true. It applies to undirected graphs, multigraphs and graphs with loops alike. The corollary follows because an even sum can only contain an even count of odd numbers.

Worked Example

Take a graph with vertices A, B, C, D and edges: A–B, A–C, B–C, B–D, C–D, plus a loop at D. Degrees: deg(A) = 2, deg(B) = 3, deg(C) = 3, deg(D) = 4 (the loop counts 2). Sum = 2 + 3 + 3 + 4 = 12, and m = 6 edges, so 2m = 12 — it matches. The odd-degree vertices are B and C — exactly 2, an even count, as the corollary promises. Without the loop, deg(D) would be 2, the sum 10, and 2m = 2 × 5 = 10 — still matching.

Common Misconceptions

• A loop counts as 1, not 2. Many students count a loop once, but the handshaking lemma only works if a loop adds 2 to the degree, since both of its ends touch the same vertex.
• An odd sum of degrees is impossible. If your degree total comes out odd, you miscounted — the sum must equal 2m, which is always even. Recheck rather than accepting it.
• "Odd number of odd vertices" is also impossible. The corollary says odd-degree vertices always come in pairs. In a party, the number of people who shook an odd number of hands is always even — try it with any group.

Real-World Applications

• Network design: checking that a drawn network diagram is consistent before building it.
• Chemistry: in a molecular graph, each atom's degree equals the number of bonds it forms; the lemma cross-checks structural formulas.
• Social network analysis: degree measures popularity; the lemma validates crawled friendship data.

The degree of a vertex is just a count of the edges touching it, and the handshaking lemma ties them together: the degrees always sum to twice the number of edges. That one equation is a fact-checker, a puzzle-solver and the starting point of most of graph theory.