Part II: Vertex Degrees

The previous chapter introduced you to vertex degrees; in this part of the book, you will learn much more about what can be done with them.

Chapter 5 will tell you about regular graphs: graphs where every vertex has the same degree. We will determine when regular graphs exist, solving our first case of the graphic sequence problem, and try to get a feeling for how many different regular graphs exist of each possible degree. Finally, we will look at the degree/diameter problem, where regular graphs play a prominent role.

In Chapter 6, we will take a closer look at the graphic sequence problem. Coming out of this chapter, you should be able to determine whether a graph with a given degree sequence exists, as well as understand the proof that our method always works.

Chapter 7 extends our definition of graphs in two different ways: to multigraphs, and to directed graphs. (It appears in this part of the chapter because it is a necessary prerequisite to fully understand Chapter 8, and because one of the important things to understand about the new definitions is how they interact with vertex degrees.) Multigraphs will play a small role throughout the rest of the book, and directed graphs will instead play an important role in several chapters.

Chapter 8 introduces Euler tours of graphs. The problem of determining whether a graph has an Euler tour has a surprising solution: almost all the information we need is contained in the degree sequence of the graph!