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 $G$, we have that ${\sum }_{v\in G}deg(v)=2|E(G)|$

Proof. Every edge $e=uv$ has 2 ends, so when we sum the degrees of the vertices, we are counting each edge twice, once at each end (once in $deg(u)$, once in $deg(v)$).

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 $G$ be a connected planar graph with a planar embedding, where $F$ is the set of all faces. Then

${\sum }_{v\in F}deg(v)=2|E(G)|$

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.

Related

• Bipartite Graph