Handshaking Lemma

graph-theory

Definition

Handshaking Lemma

In a simple undirected graph $G$, it holds that:

$$\sum _{v\in V(G)}d(v)=2\cdot \left|E(G)\right|$$

where $d(v)$ is the degree of $v$.

In a directed graph $G$, it holds that:

$$\sum _{v\in V(G)}{d}^{+}(v)=\sum _{v\in V(G)}{d}^{-}(v)=\left|E(G)\right|$$