> [!Lemma] Lemma (Handshaking lemma) > In a simple (no loops), undirected [[Graphs|graph]] $G=(V,E)$, $\sum_{v\in V} \deg (v) = 2 \cdot |E|$ *Proof* every edge has two edges so the sum counts every edge twice. # Applications Synthesis: together with ... this gives that an undirected graph must have a number of odd nodes.