Graph Theory

Handshaking Lemma

Learned in MATH239. This lemma tells us that the sum of the degrees of the vertices in a given graph is equal to the twice the number of edges.

Handshaking Lemma

For every graph , we have that

Proof. Every edge has 2 ends, so when we sum the degrees of the vertices, we are counting each edge twice, once at each end (once in , once in ).

There’s a very interesting corollary that comes from this, because you notice that the sum of the degrees is always an even number. You can still have vertices with odd degrees, but there is an even number of them:

Corollary 1.

The number of vertices of odd degree in any graph is even.

#todo Is there a relationship between the number of vertices and the number of edges?

For Planar Graph:

Faceshaking Lemma (Handshaking Lemma for Faces)

Let be a connected planar graph with a planar embedding, where is the set of all faces. Then

Proof. Each edge has 2 sides, and each side contributes to 1 to a boundary walk, so the edge contributes 2 to the sum of degrees.