Graph Theory Exercises


grafo de Petersen


This is the website of the text Graph Theory Exercises [download [pdf]] organized by Paulo Feofiloff.  The original was written in Portuguese; the English version was provided by Murilo Santos de Lima (School of Computer Science, Reykjavík University).

Graph theory and its language are used in many areas of Computer Science, Mathematics, and Engineering since graphs are a good model for many fundamental problems in these areas.

The exercises in the collection were extracted from many different books on graph theory.  The text was used a number of times in the Master's program in Computer Science at the Institute of Mathematics and Statistics of the University of São Paulo, Brazil.

A central concern of graph theory is the construction of efficient algorithms for the solution of problems on graphs.  However, the present collection of exercises takes a less algorithmic and a more structural approach. A typical question is what structural characteristics guarantee that a graph has a given property?