handshake lemma

We recall that the degree (sometimes called valency) of a vertex $v$ of an undirected graph $G$ is the number $\delta (v)$ of $v$’s neighbors, i.e., the number of vertices $z$ of $G$ such that an edge $(v,z)$ exists.

Theorem 1 (Handshake lemma)

Let $G\mathrm{=}\mathrm{(}V\mathrm{,}E\mathrm{)}$ be a simple nondirected finite graph. Then

$$\sum _{v\in V}\delta (v)=2|E|.$$ (1)

Proof. List all the edges of $G$, with their endpoints, each edge once. Each vertex $v$ occurs a number of times equal to the number of edges $v$ is an endpoint of, i.e., the number $\delta (v)$ of its neighbors. On the other hand, each edge has two endpoints, thus the sum of all occurrences of vertices must equal twice the number of edges. $\mathrm{\square }$

Theorem 2

A simple finite undirected graph has an even number of vertices of odd degree.

Proof. By the handshake lemma, the sum of the degrees of all vertices of odd degree must be even, which is only possible if their number is even. $\mathrm{\square }$

The following two statements about trees also follow from the handshake lemma. Recall that the maximum degree of a node in a finite tree cannot exceed the number of leaves of the tree, because each subtree of any node contains at least one leaf.

Theorem 3

A finite tree with exactly three leaves is homeomorphic to $K_{\mathrm{1}\mathrm{,}\mathrm{3}}$.

Proof. A finite tree with three leaves can have no vertex of degree greater than 3. By the handshake lemma, the number of vertices of odd degree must be even: this forces a vertex of degree 3 to exist. Such a vertex is also unique, because if there were two, the tree would have at least four leaves. All the other vertices, except the leaves, have degree 2, and it is possible to contract them all to get $K_{1,3}$; such a sequence of contractions is in fact a graph homeomorphism. $\mathrm{\square }$

Theorem 4

A finite tree with exactly four leaves is homeomorphic to either $K_{\mathrm{1}\mathrm{,}\mathrm{4}}$ or two joint copies of $K_{\mathrm{1}\mathrm{,}\mathrm{3}}$.

Proof. If a vertex of degree 4 exists, then no other vertex of degree greater than 2 can exist, or the tree would have five or more leaves. Otherwise, a vertex of degree 3 must exist, or the tree would be a streamline with only two leaves; by the handshake lemma, there must be another one, and no more, or the tree would have at least five leaves. All the other vertices, except the leaves, have degree 2, and it is possible to contract them all to get either $K_{1,4}$ (if there is a vertex of degree 4) or two joint copies of $K_{1,3}$ (if there are two vertices of degree 3); such a sequence of contractions is in fact a graph homeomorphism. $\mathrm{\square }$

Title	handshake lemma
Canonical name	HandshakeLemma
Date of creation	2013-03-22 18:01:52
Last modified on	2013-03-22 18:01:52
Owner	Ziosilvio (18733)
Last modified by	Ziosilvio (18733)
Numerical id	10
Author	Ziosilvio (18733)
Entry type	Theorem
Classification	msc 05C99