# IS this proof by induction of the hand shake lemma correct?

Proof by induction that the sum of degrees of vertexes in an undirected graph equals two times the number edges, where $V$ is the set of vertexes and $E$ is an edge multiset:

$$\sum_{v ∈ V} deg(v) = 2|E|$$

Basis case:

If $|E| = 0$, then the degree of each vertex is zero, and $\sum_{v ∈ V} deg(v) = 0 = 2|E|$.

Induction hypothesis:

Assume that $\sum_{v ∈ V} deg(v) = 2|E_n|$ holds for some graph with $|E_n|$ edges.

Induction step:

Add a new edge $e$ between any vertexes $v_1$ and $v_2$ of $V$ to $E_n$. If $v_1 ≠ v_2$, then the degrees of $v_1$ and $v_2$ are both incremented by 1, and if $v_1 = v_2$, then the degree of that vertex is incremented by 2, and either way, the sum of degrees is now incremented by 2, and since $2|E_n ∪ \{e\}| = 2|E_n| + 2$, the equality still holds.

• It looks spotless. – Ishfaaq Aug 24 '14 at 2:26
• I'd agree. It looks good – ruler501 Aug 24 '14 at 2:40