Graph Theory: Degree and Handshake Lemma

Degree and Handshake Lemma

Consider a graph where the vertices are telephones and where two vertices are connected if those phones are connected.

Then, each phone have degree $3$, so the total degree is $3 \times 5 = 15$.

Thus, since $15$ is odd, the scenario is impossible.

The same is true in general :

For every (simple) graph, the total degree of vertices is twice the number of edges in the graph.

The proof is similar as what we explained above.

This is also known as the Handshake Lemma.

A corollary of this lemma is that the total degree of vertices in a simple graph must be even.