Introduction to graph theory/Proof of Theorem 1

Statement

edit

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

Proof

edit

Let   incident with  . We will count the number of elements of   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   is the vertex-part of precisely   elements of  . Thus the number of elements of   is the sum of the degrees of the vertices.

The other obvious way to count the number of elements of   is in terms of the edges. Clearly each edge is incident with precisely two vertices. Therefore edge   is the edge-part of precisely 2 elements of  . Thus the number of elements of   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

edit

In combinatorics, you can prove most results a number of different ways. Here is an alternate proof by induction on the number of edges  . If  , 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   edges, and that graph   has   edges. Let   be an edge of  . Denote by   the graph identical to   in all respects, save the omission of the edge  . Then clearly   has   edges, and so its degrees sum to  .   has identical degrees to  , except for an increase by one at the vertices   and  . Thus the sum of the degrees of   is  , proving the theorem by induction.

Comments

edit

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