Introduction to graph theory/Proof of Theorem 1
Statement[edit | edit source]
The sum of the degrees of the vertices of a graph is precisely twice the size of .
Proof[edit | edit source]
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 | edit source]
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 | edit source]
The method of double counting is often used in Combinatorics, and is worth getting to know well.