The Handshaking Lemma

Graph Theory · Axiom Academy

A fundamental theorem in graph theory that connects vertex degrees to edge count The Handshaking Lemma states that in any graph G = (V, E), the sum of all vertex degrees equals twice the number of edges: Where deg(v) represents the degree of vertex v (the number of edges incident to it), and |E| is the total number of edges in the graph. 2. Why Does Each Edge Contribute 2? The key insight is that every edge connects exactly two vertices. When we count degrees, each edge gets counted twice: once at each endpoint. Think of it this way: if you have an edge between vertices u and v, it contributes +1 to deg(u) and +1 to deg(v), for a total contribution of 2 to the sum. Imagine a party where people shake hands. Each handshake involves exactly two people. If we ask each person "How many hands did you shake?", the sum of all their answers must be even. Why? Because each handshake gets counted twice: once by each participant. If there were h handshakes total, the sum of individual counts is 2h. 4. Corollary: The Sum of Degrees is Always Even Since the sum of all degrees equals 2|E|, and 2|E| is always an even number (it's 2 times something), we have an immediate consequence: This means no matter what graph you have, when you add up all the vertex degrees, you'll always get an even number. 5. Corollary: Even Number of Odd-Degree Vertices Here's a surprising consequence: in any graph, the number of vertices with odd degree must be even.

This is the written version of the interactive lesson above. See the full Graph Theory course.