Proof that the sum of all degrees is equal to twice the number of edges

We want to proof $2|E| = \sum \limits_{v \in V} deg(v)$ for a simple graph (no loops). For our proof we assume $n$ to be the number of edges in a simple graph $G(E, V)$. We proceed our proof by induction.

Base case P(0), no edges exist, so all nodes in $G$ have degree 0. Therefore we find that $2n = 2 * 0 = \sum deg(v) = 0$

Inductive step, assuming P(n) is true, we need to show that P(n + 1) is also true, that is:

$2(n + 1) = \sum \limits_{v \in V} deg(v)$

In a graph $G$ with number of edges $n + 1$. If we remove one edge at random $G$, we get a subgraph $G'(E',V')$ for which we can assume P(n):

$2n = \sum \limits_{v \in V'} deg(v)$

$G$ is equal to the subgraph $G'$ plus one edge. As every edge contributes $2$ to the total number of degrees (as every edge connects two vertices) we can say for $G$:

$2n + 2 = 2(n + 1) = \sum \limits_{v \in V'} deg(v)$

Which proofs P(n + 1).

Does the above proof make sense? I had a look at some other questions, but couldn't find a fully written proof by induction for the sum of all degrees in a graph.

Solution 1:

Whenever an edge is introduced in a graph; It will connect two nodes (vertices). So degree of both those nodes will increase by $1$.

Thus Sum of degrees will increase by $2$.

So we can say that every addition of edge increases sum of degrees by $2$.

So if there are $E$ such edges: sum of degrees $= 2 + 2 + 2 \ldots$ ($E$ times) = $2E$.

Solution 2:

Consider a table whose rows are labelled by edges, and whose columns are labelled by vertices. For each edge, put a mark in the two columns corresponding to the vertices of that edge. Example: if you have a square $ABCD$ with the diagonal $AC$ added in, the table looks like this:

    A   B   C   D
AB  *   *
BC      *   *  
CD          *   *
DA  *           *
AC  *       *

Now compute the row- and column-sums for the table:

    A   B   C   D  sum
AB  *   *          2
BC      *   *      2
CD          *   *  2
DA  *           *  2
AC  *       *      2
sum 3   2   3   2

The columns sums are exactly the vertex degrees; the row sums are all twos. The sum of the column sums is therefore the total degree; the sum of the row sums is twice the number of edges. But each of these corresponds to the total number of marks in the table, hence they must be equal. We conclude that the sum of the degrees is twice the number of edges.

(This is really just @MarianoSuárez-Álvarez's one-liner proof from the comments written out in a more visual form, by the way.)