Introduction to graph theory/Proof of Theorem 1

Statement

The sum of the degrees of the vertices of a graph $G$ is precisely twice the size of $G$.

Proof

Let $S=\{(v,e):v\in V(G),e\in E(G),v$ incident with $e\}\!\,$. We will count the number of elements of $S$ in two different ways, using the method of double counting.

The degree of a vertex is defined to be the number of edges incident with that vertex. Therefore vertex $v$ is the vertex-part of precisely $d(v)$ elements of $S$. Thus the number of elements of $S$ is the sum of the degrees of the vertices.

The other obvious way to count the number of elements of $S$ is in terms of the edges. Clearly each edge is incident with precisely two vertices. Therefore edge $e$ is the edge-part of precisely 2 elements of $S$. Thus the number of elements of $S$ is twice the number of edges.

Since a set has the same number of elements, regardless of how you count them (unless, of course, you miscount them), it follows that the sum of the degrees of the vertices is twice the number of edges.

Alternate Proof

In combinatorics, you can prove most results a number of different ways. Here is an alternate proof by induction on the number of edges $m$. If $m=0$, there are no edges and hence each degree is 0, so the total of the degrees is indeed twice the number of edges.

Now suppose that we have proved the theorem for all graphs with $m-1$ edges, and that graph $G$ has $m$ edges. Let $uv$ be an edge of $G$. Denote by $G-uv$ the graph identical to $G$ in all respects, save the omission of the edge $uv$. Then clearly $G-uv$ has $m-1$ edges, and so its degrees sum to $2m-2$. $G$ has identical degrees to $G-uv$, except for an increase by one at the vertices $u$ and $v$. Thus the sum of the degrees of $G$ is $(2m-2)+2=2m$, proving the theorem by induction.

Comments

The method of double counting is often used in Combinatorics, and is worth getting to know well.