gen-define-the-handshake-lemma-and-give-one-short-worked-example-d146

Define the handshake lemma and give one short worked example.

# Handshake Lemma ## Definition The **Handshake Lemma** states that in any graph, the sum of all vertex degrees equals twice the number of edges: $$\sum_{v \in V} \deg(v) = 2|E|$$ **Intuition:** Each edge contributes 1 to the degree of each of its two endpoints, so every edge is counted exactly twice in the sum of degrees. **Corollary:** The sum of all vertex degrees is always even, which means there must be an even number of vertices with odd degree. ## Worked Example Consider a graph with 5 vertices where: - Vertex A has degree 3 - Vertex B has degree 2 - Vertex C has degree 2 - Vertex D has degree 1 - Vertex E has degree 2 **Find the number of edges.** **Solution:** $$\sum \deg(v) = 3 + 2 + 2 + 1 + 2 = 10$$ By the Handshake Lemma: $$2|E| = 10$$ $$|E| = 5$$ Therefore, the graph has **5 edges**.