17
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Consider the set P of all pairs (v,e) with v a vertex and an edge such that e touches v. There is a surjective function f: P -> E to the edge of sets mapping each pair (v,e) to e, and the preimage of each element of E by f consists of two points: this means that P has twice as many elements as E. Now there is a function g: P -> V, With V the set of vertices mapping each pair (v,e) to the vertex V. How many elements are in the preimage of a vertex under g? $\endgroup$ Commented Aug 17, 2017 at 5:39
  • $\begingroup$ In any case, your argument is correct. $\endgroup$ Commented Aug 17, 2017 at 5:43
  • $\begingroup$ Correct, but suppose you had no idea what your candidate solution would be. If you were looking at the degrees, you may note that each edge has two vertices it's connected with, therefore you always count the same edge exactly twice, hence the result. $\endgroup$
    – AlvinL
    Commented Aug 17, 2017 at 5:51
  • $\begingroup$ @Mariano Suárez-Álvarez, the claim is overwhelmingly complex, as the induction proof, btw. Each edge is counted exactly twice in sum of all degrees, cause it have two ends (incl. self loops). $\endgroup$
    – dEmigOd
    Commented Aug 17, 2017 at 6:06
  • $\begingroup$ What is overwhelmingly complex?! $\endgroup$ Commented Aug 17, 2017 at 6:10

2 Answers 2

14
$\begingroup$

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$.

$\endgroup$
0
1
$\begingroup$

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.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .