📂Graph Theory

Shaking Hands Dilemma Proof

Theorem ¹

In any directed graph, the sum of the in-degrees and the sum of the out-degrees are equal.

Explanation

The handshake dilemma can be considered the handshake lemma for directed graphs.

Proof

In a directed graph, the sum of the out-degrees is equal to the number of arcs. Since an arc comes out from one vertex and enters another, the sum of the out-degrees and in-degrees are equal.

■