Handshaking lemma

In any finite undirected graph, the sum of the vertex degrees equals twice the number of edges, because each edge contributes one incidence at each endpoint.

Vertex degree: The number of edges incident to a vertex in a graph. Summing this quantity over all vertices counts every edge endpoint.
Odd-degree vertex: A vertex whose degree is an odd integer. The lemma implies every graph has an even number of such vertices.
Graph (discrete mathematics): A structure consisting of vertices joined by edges. The lemma is a universal counting fact about finite undirected graphs.
Graph theory: The mathematical study of graphs and their properties. The lemma is a basic counting tool used throughout the subject.
Incidence matrix: A matrix recording which vertices are incident to which edges. Its entries encode the incidences whose total gives the degree sum.
Eulerian trail: A trail that traverses every edge of a graph exactly once. Its existence requires either zero or two vertices of odd degree.
Undirected graph: A graph whose edges have no assigned direction. Without direction, each edge has two endpoints counted in the degree sum.
Graph realization problem: The problem of determining whether a degree sequence is realized by a graph. An odd total degree sum immediately rules out a simple realization.
Graph incidence: A relation in which a vertex is an endpoint of an edge. Each ordinary edge contributes exactly two vertex-edge incidences.
Tree (graph theory): A connected acyclic graph. A tree with n vertices has n−1 edges, so its degrees sum to 2n−2.

Linked from 6 pages