Handshaking Lemma

Describes the relationship between vertex degrees and edges in a graph. Each edge contributes 1 to the degree of each of its endpoints, leading to a fundamental counting principle.

For all the definitions below, consider a graph $G$ with $n$ vertices and $m$ edges.

For Simple Graphs

Sum of all vertex degrees equals twice the number of edges.

Applies for connected components as well.

Corollary

The number of vertices with odd degree is always even.

For Digraphs

Sum of in-degrees equals sum of out-degrees, both equal to the number of edges.