Graph Theory Lessons

Answers to Lesson 2

  1. The sum of the degrees of the vertices is twice the number of edges. This is because an edge from vertex vi to vertex vj contributes 1 to the degree of vi and 1 to the degree of vj and therefore 2 to the sum of the degrees.

  2. No, it is not possible for the sum of degrees to be an odd number. The sum of the degrees is always even since in question 1 we found that it is twice the number of edges.

  3. Let E be the set of vertices with even degrees and let O be the set of vertices with odd degrees. Then the sum of the degrees of the vertices can be thought of as
    The first sum is always even since deg(v) is even for all the vertices The second sum is a sum of odd numbers. Now the sum of an odd nmber of odd numbers is odd, while the sum of an even number of odd numbers is even. So in order for the sum of all the degrees to be even the number of vertices in O must be even.

  4. Since the graph has 15 edges, the sum of the degrees is 30. Now the three vertices of degree 4 contribute 12 to this sum so the ones of degree 3 must contribute 18. We therefore need 6 vertices of degree 3, giving a total of 9 vertices.

  5. If we represent the nine people by nine vertices and if we draw an edge between two vertices whenever the people they represent are aquainted we get a graph with nine vertices of degree 5. This is impossible as we would then have an odd number of odd degree vertices.

  6. First notice that if we have a graph on n vertices them the maximum degree a vertex in that graph can have is n - 1, and the minimum possible degree is 0. So we can use the n numbers 0,1,...,n - 1 as possible degrees for the n vertices. Suppose that no two vertices have the same degree. Then we must have one vertex of degree 0, one vertex of degree 1,..., and one vertex of degree n - 1. However, it is impossible to simultaneously have a vertex of degree 0 and a vertex of degree n - 1 because a vertex of degree n - 1 needs to have an edge going to every other vertex in the graph making every other vertex have degree at least 1. [Note that here we argued by first assuming that a statement is true, i.e. that it is possible for all the vertices to have different degrees and then we showed that it leads to something we know to be false. This is called a proof by contradiction].

  7. An example of a non simple graph with four vertices that has all vertices of different degree is
e-mail: C. Mawata
© C. Mawata