Graph Theory Lessons

A graph in which every vertex has the same degree is called a regular graph. If every vertex has degree r then we say the graph is regular of degree r . All null graphs are regular of degree zero.

1. If a graph with n vertices is regular of degree r, what is the sum of the degrees of the vertices?

2. If a graph with n vertices is regular of degree r, how many edges does it have? (Use your answer to question 1 of Exercise 2)

3. Look at the statistics of a few complete graphs. Is the complete graph K_n regular, and if so of what degree?

4. From your answer to part 1 and 3, what is the sum of degrees for K_n?

5. From your answers to questions 4 and 2, how many edges will K_n have?

6. A trivalent graph is one that is regular of degree 3. Which of the complete graphs is/are trivalent?

7. A very well known graph is the Petersen Graph. It is the graph that this program is named after.



Fig. 7, The Petersen Graph



To get the Petersen Graph click Graph and then Petersen. Is the Petersen Graph a regular graph? Is it trivalent?
8. Sketch a simple trivalent graph with six vertices.

Answers