Handshaking Lemma

graph-theory

Definition

Handshaking Lemma (Simple Undirected)

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$.

Handshaking Lemma (Directed)

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

Proof

Proof (Simple Undirected)

In a simple undirected graph, every edge $e=\{u,v\}$ is incident to exactly two vertices, namely $u$ and $v$. Hence, when summing the degrees over all vertices, each edge is counted exactly twice: once in $d(u)$ and once in $d(v)$. Therefore,

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