The Handshaking Dilemma

Lemma 1 (The Handshaking Dilemma): For a digraph $G = (V(G), E(G))$, the sum of all of the out-degrees in a graph is equal to the sum of all of the in-degrees in a graph.

We can write this lemma mathematically in the following way:

(1)

\begin{align} \sum_{x \in V(G)} \mathrm{outdeg}(x) = \sum_{x \in V(G)} \mathrm{indeg}(x) \end{align}

We will now prove Lemma 1.

• Proof: In any graph, an arc has two ends with one end of the arc adding $1$ to the out-degree of some vertex in $V(G)$, while the other end of the arc adding $1$ to the in-degree of some vertex in $V(G)$. Hence, the proof is complete. $\blacksquare$

Let's look at the following graph:

The out-degrees of each vertex are in blue, while the in-degrees of each vertex are in red. The out-degree sequence is $(0, 0, 1, 1, 2, 2, 3, 3)$ while the in-degree sequence is $(0, 1, 1, 1, 2, 2, 2, 3)$. Thus:

(2)

\begin{align} \sum_{x \in V(G)} \mathrm{outdeg}(x) = \sum_{x \in V(G)} \mathrm{indeg}(x) \\ 0 + 0 + 1 + 1 + 2 + 2 + 3 + 3 = 0 + 1 + 1 + 1 + 2 + 2 + 2 + 3 \\ 12 = 12 \end{align}