Handshake Lemma

From ProofWiki
Jump to navigation Jump to search


Theorem

Let $G$ be a $\left({p, q}\right)$-graph, which may be a multigraph or a loop-graph, or both.

Let $V = \left\{{v_1, v_2, \ldots, v_p}\right\}$ be the vertex set of $G$.


Then:

$\displaystyle \sum_{i \mathop = 1}^p \deg_G \left({v_i}\right) = 2 q$

where $\deg_G \left({v_i}\right)$ is the degree of vertex $v_i$.


That is, the sum of all the degrees of all the vertices of a graph is equal to twice the total number of its edges.


This result is known as the Handshake Lemma or Handshaking Lemma.


Corollary

The number of odd vertices in $G$ must be even.


Proof

In the notation $\left({p, q}\right)$-graph, $p$ is its order and $q$ its size.

That is, $p$ is the number of vertices in $G$, and $q$ is the number of edges in $G$.

Each edge is incident to exactly two vertices.

The degree of each vertex is defined as the number of edges to which it is incident.

So when we add up the degrees of all the vertices, we are counting all the edges of the graph twice.

$\blacksquare$


Historical Note

This result was first given by Leonhard Euler in his 1736 paper Solutio problematis ad geometriam situs pertinentis, widely considered as the first ever paper in the field of graph theory.


Sources