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)
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)