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 timesequal 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 verticesmust equal twice the number of edges.$\mathrm{\square }$

Theorem 2

A simple finite undirected graphhas 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 treecannot 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 leavesis 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 leavesis 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 allto 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 }$