Graph Theory Lessons

Answers to Lesson 5

  1. If a graph with n vertices is regular of degree r, then, using deg(i) to represent the degree of vertex vi, the sum of the degrees of the vertices is

  2. In question 1 of Lesson 2 we found that the sum of the degrees of the vertices is twice the number of edges. From question 1 of this lesson the sum of the degrees is nr. Therefore the number of edges must be nr/2.

  3. The complete graph Kn is regular of degree n - 1.

  4. If we put r = n - 1 in question 1, we get that the sum of degrees for Kn is n (n - 1).

  5. If we put r = n - 1in question 2, we get that the number of edges in Kn is n (n - 1)/2.

  6. A trivalent graph is one that is regular of degree 3. In question 3, we found that Kn is regular of degree n - 1. Therefore we must have n - 1 = 3, i.e., n = 4 The graph K4 is the only trivalent complete graph.

  7. The Petersen graph is trivalent since each of its vertices has degree 3.

  8. There are many a simple trivalent graphs with six vertices. Here is one:

e-mail: C. Mawata
© C. Mawata