structural:expansion, information:filtering
Proof

Euler's proof of the degree sum formula uses the technique of double counting: he counts the number of incident pairs (v, e) {\displaystyle (v,e)} where e {\displaystyle e} is an edge and vertex v {\displaystyle v} is one of its endpoints, in two different ways. Vertex v {\displaystyle v} belongs to deg (v) {\displaystyle \deg(v)} pairs, where deg (v) {\displaystyle \deg(v)} (the degree of v {\displaystyle v}) is the number of edges incident to it. Therefore, the number of incident pairs is the sum of the degrees. However, each edge in the graph belongs to exactly two incident pairs, one for each of its endpoints; therefore, the number of incident pairs is 2 | E | {\displaystyle 2|E|}. Since these two formulas count the same set of objects, they must have equal values. The same proof can be interpreted as summing the entries of the incidence matrix of the graph in two ways, by rows to get the sum of degrees and by columns to get twice the number of edges.

For graphs, the handshaking lemma follows as a corollary of the degree sum formula. In a sum of integers, the parity of the sum is not affected by the even terms in the sum; the overall sum is even when there is an even number of odd terms, and odd when there is an odd number of odd terms. Since one side of the degree sum formula is the even number 2 | E | {\displaystyle 2|E|}, the sum on the other side must have an even number of odd terms; that is, there must be an even number of odd-degree vertices.

Alternatively, it is possible to use mathematical induction to prove the degree sum formula, or to prove directly that the number of odd-degree vertices is even, by removing one edge at a time from a given graph and using a case analysis on the degrees of its endpoints to determine the effect of this removal on the parity of the number of odd-degree vertices.