THE HANDSHAKE — a dart

THE HANDSHAKE LEMMA the sum of degrees is twice the edges — so odd-degree vertices come in pairs

The oldest theorem in graph theory, and one of the simplest: the sum of all vertex degrees equals twice the number of edges. The reason is a single sentence — each edge has two ends, so it adds exactly 1 to two vertices’ degrees. Euler noticed it in 1736. A corollary follows for free and surprises people: the number of odd-degree vertices is always even (you cannot have an odd number of them). In social terms, at any party the number of people who have shaken an odd number of hands is even. The 5-edge graph here has degree-sum 10 = 2×5.

THE TECHNIQUE ∑ deg(v) = 2E — each edge contributes 2; odd-degree vertices are even in number

The demo sums the degrees of a 5-edge graph — the total is 10, exactly twice the edges: live demo

HISTORY & CREDIT Euler · 1736 (handshaking lemma)

“Vertex degrees are unconstrained.” — their sum is exactly twice the edges, so the odd-degree count is always even. cited

the lemma · ∑ deg(v) = 2E — each edge adds 1 to two vertices.
the corollary · the number of odd-degree vertices is even — they pair up.
1736 · Euler — the first theorem of graph theory (with the Königsberg bridges).

Every edge counted twice in the degrees — so odd handshakers always come in pairs. theorem

RECOMMEND FOR I-13 the degree sum, on the compiler

On the canonical compiler, the 5-edge graph has degree-sum 10 = 2×5:

$ i13 run nw_handshake.i13 # sum of degrees vs 2E RUN OK · 765 step(s) · peak stack 25 · call depth 11 degsum = 10 edges = 5 handshake = 1 -- degsum == 2 * edges

Recommend as a NULL — a theorem, the oldest one. The handshaking lemma is an identity every graph obeys (∑deg = 2E, B39), coextensive with the definition of degree. i13 confirms it (10 = 2×5). Not a mechanism a keeper enacts. NULL — and the ground the Euler-path dart (531) stands on.