Answer to Question #222055 in Discrete Mathematics for Sach

Question

Show that that sum of the degrees of the vertices in a graph is twice the number of edges in the graph.

Answer 1

Solution:

Proof:

We can also prove the claim using induction on the number of edges. Let us reformulate the claim in a way that makes clear all of the parameters in the problem. We are trying to prove the claim that in a graph G with n vertices and m edges, that:

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

Base Case: m = 0

Let G be an arbitrary graph with n vertices and 0 edges. Note that the degree of each vertex in the graph must be 0, since there are no edges. Thus, the sum of the degree of all of the vertices must also be 0.

Induction Hypothesis: Assume that, for some k ∈ N, an arbitrary graph with n vertices and k edges has the following property:

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

Induction Step: Let G(V, E) be an arbitrary graph with n vertices and k + 1 edges. Consider the graph G' (V' , E' ) that is the graph constructed by removing an arbitrary edge e = {u, v} from G. Note that G' is a graph with n vertices and k edges. By the Induction Hypothesis, we know that:

$\sum_{v \in V^{\prime}} \operatorname{deg}(v)=2\left|E^{\prime}\right|$

 Thus, proved.