Degree sum formula

The degree sum formula is a fundamental theorem of graph theory which states that, given a graph G=(V,E),

$\sum_{v \in V} \deg(v) = 2|E|.$

The formula implies that in any graph, the number of vertices with odd degree is even.

[edit] Proof

Each edge is incident to two vertices and contributes exactly 2 to the sum of the degrees.

This topology-related article is a stub. You can help Wikipedia by expanding it.