Handshake Lemma

From ProofWiki
Jump to navigation Jump to search


Theorem

Let $G$ be a $\tuple {p, q}$-undirected graph, which may be a multigraph or a loop-graph, or both.

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


Then:

$\displaystyle \sum_{i \mathop = 1}^p \map {\deg_G} {v_i} = 2 q$

where $\map {\deg_G} {v_i}$ is the degree of vertex $v_i$.


That is, the sum of all the degrees of all the vertices of an graph is equal to twice its size.


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


Corollary

The number of odd vertices in $G$ is even.


Proof

In the notation $\tuple {p, q}$-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$


Examples

Arbitrary Order $8$ Graph

Chartrand-exercise-2-1-1.png

The above simple graph has $8$ vertices and $10$ edges (which can be ascertained by counting).

\(\displaystyle \map \deg {v_1}\) \(=\) \(\displaystyle 2\)
\(\displaystyle \map \deg {v_2}\) \(=\) \(\displaystyle 3\)
\(\displaystyle \map \deg {v_3}\) \(=\) \(\displaystyle 3\)
\(\displaystyle \map \deg {v_4}\) \(=\) \(\displaystyle 3\)
\(\displaystyle \map \deg {v_5}\) \(=\) \(\displaystyle 4\)
\(\displaystyle \map \deg {v_6}\) \(=\) \(\displaystyle 1\)
\(\displaystyle \map \deg {v_7}\) \(=\) \(\displaystyle 2\)
\(\displaystyle \map \deg {v_8}\) \(=\) \(\displaystyle 2\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \sum \map \deg V\) \(=\) \(\displaystyle 2 + 3 + 3 + 3 + 4 + 1 + 2 + 2\)
\(\displaystyle \) \(=\) \(\displaystyle 20\)
\(\displaystyle \) \(=\) \(\displaystyle 2 \times 10\)


Impossible Order $6$ Graph

There exists no undirected graph whose vertices have degrees $2, 3, 3, 4, 4, 5$.


No Graph with One Odd Vertex

There exists no undirected graph with exactly one odd vertex.


Historical Note

The Handshake Lemma was first given by Leonhard Euler in his $1736$ paper Solutio problematis ad geometriam situs pertinentis.

This is widely considered as the first ever paper in the field of graph theory.


Sources