Size vs. Degree
Mathematicians love to generalize. In this section we'll look at a couple of basic properties that are true of all graphs no matter what their size or order. First we need a new word.
What You Should Learn
Let G be a graph and let v be one of its vertices. The degree or v is equal to the number of edges incident to v. We write this as deg v.
The degree of a vertex is simply the number of edges that connect to the vertex.
Look at the graph on the right. (It's the one from the first section.) Because there is only one edge going to vertex v1 its degree must be 1. We would write this deg v1 = 1. If you count up the edges going to the other vertices you get:
deg v2 = 2
deg v3 = 3
deg v4 = 1
deg v5 = 3
If you add up all of the degrees you get 1 + 2 + 3 + 1 + 3 = 10. But the size of the graph1 is 5 so in this case the sum of the degrees of the graph's vertices is twice its size. Is this a coincidence? Go back and look at the graphs from previous sections and see if it's true for them. Try drawing some random graphs of your own and see if it's true for them. This brings us to our first theorem:
If G is a graph then the sum of the degrees of its vertices is equal to twice its size.
Let e be an edge. Because this edge has to touch two vertices it contributes 2 to the total of the graph's degrees. Because every edge counts twice toward the total of the graph's degrees but only once toward the size it follows that the total of the graph's degrees is twice the number of edges, i.e. the size.
That leads us to a slightly less intiutive conclusion. The statement can be a little confusing so start by reading it slowly. If you still don't quite get it jump to the non-technical section below where we'll look at some examples.
Every graph has an even number of odd vertices. (By an "odd vertex" I mean one whose degree is an odd number.)
First we need to define some variables. Let o1, ..., on be the odd vertices and let O = deg o1 + ... + deg on be the sum of the degrees of the odd vertices. Now let v1, ...,vm be the even vertices and let V = deg v1 + ... + deg vm be the sum of the degrees of the even vertices. (Why did I use v instead of e? We usually use e to refer to edges and I wanted to avoid any possible confusion.)
Because O + V is the sum of the degrees of the graph's vertices, the previous theorem tells us that O + V = 2E where E is the number of edges in the graph, i.e. the size of the graph. This means that O + V is an even number. It also means that O is an even number because O = 2E - V. (V is even because it's the sum of a set of even numbers and 2E - V is even because it's the difference of two even numbers.)
Before we go any further you need to understand some basic properties of odd and even numbers. First, notice that the sum of two even numbers is an even number. Second, notice that the sum of an odd number and an even number is an odd number. (To convince yourself, try looking at some examples.) Now think about O. Remember that it's equal to the sum of a group of odd numbers, the degrees of the odd vertices. But, in the last paragraph we showed that it has to be even. In order for a set of odd numbers to add up to an even number there must be an even number of them. But this is what we wanted to prove - that there are an even number of odd vertices.
Here's another way to think of the last step: There can't be only one vertex because then O would be equal to that vertex's degree which is an odd number. This can't happen because we know O is even. So we know there has to be at least two odd vertices. If we add those degrees together we get an even number. Suppose there's a third odd vertex. If we add it to the even number that we got by adding the previous two vertices together we get an odd number. Again this can't happen because we know O is even so there must be a fourth vertex. You can continue this process indefinitely to show that the statement is true for any size graph.