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

### 1 Answer | Add Yours

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:**