Existing in Mathlib · Graph theory

Handshaking Lemma

In every finite undirected simple graph, the number of vertices incident to an odd number of edges is even.

handshaking lemma
finite simple graphs
vertex degree
degree-sum formula
parity
double counting

Exact theorem

Exact Mathlib statement

theorem SimpleGraph.even_card_odd_degree_vertices {V : Type*} (G : SimpleGraph V) [Fintype V] [DecidableRel G.Adj] : Even #{v | Odd (G.degree v)}

The theorem at a glance

Handshaking lemma at a glance

A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.

An ivory handshaking-lemma poster states the even-cardinality endpoint above an exact eight-vertex, ten-edge example. Four double-ringed vertices have degree three, the other four have degree two, and a three-stage route moves from the degree sum through reduction modulo two to even parity. — Each undirected edge contributes two endpoint incidences, so reducing the degree sum modulo two leaves an even number of odd-degree vertices.

Accessible poster text

Read the headline and panel text

GRAPH THEORY · PARITY

HANDSHAKING LEMMA

IN A FINITE SIMPLE GRAPH

THE NUMBER OF ODD-DEGREE VERTICES IS EVEN

Even #{v | Odd (degree v)}

A COUNT-EXACT EXAMPLE

v₁ · v₂ · v₃ · v₄ · v₅ · v₆ · v₇ · v₈

degrees: 3 · 2 · 2 · 3 · 3 · 2 · 2 · 3

4 odd-degree vertices

10 undirected edges

20 endpoint incidences

× 10

degree sum

20 = 2×10

THE CHECKED ROUTE

1 · SUM THE DEGREES

∑ degree(v) = 2|E|

2 · REDUCE MODULO 2

even terms vanish · odd terms count as 1

3 · CLOSE THE PARITY

#{v | Odd (degree v)} ≡ 0 (mod 2)

EXACT SCOPE

Finite vertex type · undirected simple graph.

The theorem allows 0, 2, 4, … odd-degree vertices.

It does not pair them by edges or classify all graphs.

The detailed visual description covers the diagram and its local mathematical labels.

Statement structure

From hypotheses to conclusion

This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.

An unlabeled octagonal graph has eight circular vertices and ten edges: eight perimeter edges plus a vertical chord from top to bottom and a horizontal chord from left to right. The four chord endpoints have emerald centers and double gold rings; the four diagonal vertices are ivory with single charcoal rings. The chord crossing has no vertex. — In this eight-vertex example, the four chord endpoints have degree three and the other four vertices have degree two, so the odd-degree set has four members.

Why it matters

A mathematical landmark

The handshaking lemma is a foundational parity invariant in graph theory. Mathlib's selected declaration records the familiar odd-degree endpoint, with the degree-sum formula and a concise reduction modulo two exposed directly in the checked source.

ProofAtlas record

What has been checked

Upstream indexedPinned source bytes verified locally

Locally reproducedExact upstream declaration replayed

Reviewed pageCurrent public presentation reviewed

Accepted Atlas resultNot recorded for the preferred artifact

Mathlib is the source of the theorem; the local Lean replay and page review are separate.

Claim boundary

No new theorem is claimed

This page indexes Mathlib's odd-degree parity form of the handshaking lemma. For a simple graph G on a finite vertex type V, with decidable adjacency, the selected declaration concludes Even #{v | Odd (G.degree v)}. The degree-sum identity is a supporting declaration in the checked route, not the selected endpoint. The result allows zero odd-degree vertices and does not prescribe an exact positive number, pair odd vertices by edges, require connectivity, or classify finite graphs.

ProofAtlas did not originate the handshaking lemma or Mathlib's declaration.
The selected endpoint is even cardinality of the odd-degree vertex set; the supporting degree-sum identity is not substituted for it.
The theorem does not assert that every graph has exactly two or four odd-degree vertices.
It does not pair odd-degree vertices by actual graph edges.
It does not require the graph to be connected or classify finite simple graphs.
The generated explanation and visuals are not proof evidence.

Source and local evidence

Where the theorem comes from

Existing declaration: SimpleGraph.even_card_odd_degree_vertices in mathlib
Relationship: The checked artifact is the upstream declaration itself
Local Lean evidence: artifact.library.mathlib.handshaking-lemma.v001
Source: Open the pinned upstream reference