prove that the sum of the degrees of the points of a graph G is twice the number of lines.

Asked on by mingma

1 Answer |Add Yours

Matthew Fonda | eNotes Employee

Posted on

This was proven by Euler (1736) in his famous solution to the Seven Bridges of Königsberg problem. This same work is also considered to be the origin of graph theory.

I will give an overview of Euler's proof:

We want to show that for a graph G = (V,E)

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

We use the technique of double-counting. We will count the number of pairs (v, e), where e is an edge, and v is one of its endpoints. Each vertex v has is in deg(v) pairs, since this is the number of edges leaving v. Therefore the total number of such pairs (v, e) is

sum_{v \in V} deg(v)

Next, we notice that each edge e is in two pairs, since each edge has two endpoints. Therefore the total number of such pairs (v. e) is

2|E|

Since both these quantities count the same thing, it follows that

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

Sources:

We’ve answered 319,186 questions. We can answer yours, too.