5.S: Graph Theory (Summary)

Hopefully this chapter has given you some sense for the wide variety of graph theory topics as well as why these studies are interesting. There are many more interesting areas to consider and the list is increasing all the time; graph theory is an active area of mathematical research.

One reason graph theory is such a rich area of study is that it deals with such a fundamental concept: any pair of objects can either be related or not related. What the objects are and what “related” means varies on context, and this leads to many applications of graph theory to science and other areas of math. The objects can be countries, and two countries can be related if they share a border. The objects could be land masses which are related if there is a bridge between them. The objects could be websites which are related if there is a link from one to the other. Or we can be completely abstract: the objects are vertices which are related if their is an edge between them.

What question we ask about the graph depends on the application, but often leads to deeper, general and abstract questions worth studying in their own right. Here is a short summary of the types of questions we have considered:

  • Can the graph be drawn in the plane without edges crossing? If so, how many regions does this drawing divide the plane into?
  • Is it possible to color the vertices of the graph so that related vertices have different colors using a small number of colors? How many colors are needed?
  • Is it possible to trace over every edge of a graph exactly once without lifting up your pencil? What other sorts of “paths” might a graph posses?
  • Can you find subgraphs with certain properties? For example, when does a (bipartite) graph contain a subgraph in which all vertices are only related to one other vertex?

Not surprisingly, these questions are often related to each other. For example, the chromatic number of a graph cannot be greater than 4 when the graph is planar. Whether the graph has an Euler path depends on how many vertices each vertex is adjacent to (and whether those numbers are always even or not). Even the existence of matchings in bipartite graphs can be proved using paths.

Chapter Review


Which (if any) of the graphs below are the same? Which are different? Explain.


The first and the third graphs are the same (try dragging vertices around to make the pictures match up), but the middle graph is different (which you can see, for example, by noting that the middle graph has only one vertex of degree 2, while the others have two such vertices).

Watch the video: Degree sequences - 4 (October 2021).