2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.