Editing Double counting (proof technique) (section)

===Handshaking lemma===
{{main|Handshaking lemma}}
Another theorem that is commonly proven with a double counting argument states that every [[undirected graph]] contains an even number of [[Vertex (graph theory)|vertices]] of odd [[Degree (graph theory)|degree]]. That is, the number of vertices that have an odd number of incident [[Graph (discrete mathematics)|edges]] must be even. In more colloquial terms, in a party of people some of whom shake hands, an even number of people must have shaken an odd number of other people's hands; for this reason, the result is known as the [[handshaking lemma]]. 

To prove this by double counting, let <math>d(v)</math> be the degree of vertex <math>v</math>. The number of vertex-edge incidences in the graph may be counted in two different ways: by summing the degrees of the vertices, or by counting two incidences for every edge. Therefore
<math display=block>\sum_v d(v) = 2e</math>
where <math>e</math> is the number of edges. The sum of the degrees of the vertices is therefore an [[even number]], which could not happen if an odd number of the vertices had odd degree. This fact, with this proof, appears in the 1736 paper of [[Leonhard Euler]] on the [[Seven Bridges of Königsberg]] that first began the study of [[graph theory]].