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 with vertices and 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.