[graph] Graph Theory Tutorials

Chris K. Caldwell (C) 1995

This is the home page for a series of short interactive tutorials introducing the basic concepts of graph theory. They are designed with the needs of future high school teachers in mind and are currently being used as a supplement to our Mathematical Modeling course (Math 451).

These tutorials are created using the Web Tutor so that most of the pages of this tutorial require that you pass a quiz before continuing to the next page, while others ask for a written comment. The Web Tutor must be able to keep track of your progress, so you will need to register for each of these courses by pressing the [REGISTER] button on the bottom of the first page of each tutorial. (You can use the same username and password for each tutorial, but you will need to register separately for each course.)

Introduction to Graph Theory (6 pages)
Starting with three motivating problems, this tutorial introduces the definition of graph along with the related terms: vertex (or node), edge (or arc), loop, degree, adjacent, path, circuit, planar, connected and component. [Suggested prerequisites: none]
Euler Circuits and Paths
Beginning with the Königsberg bridge problem we introduce the Euler paths. After presenting Euler's theorem on when such paths and circuits exist, we then apply them to related problems including pencil drawing and road inspection. [Suggested prerequisites: Introduction to Graph Theory]
Coloring Problems (6 pages)
How many colors does it take to color a map so that no two countries that share a common border have the same color? This question can be changed to "how many colors does it take to color a planar graph?" In this tutorial we explain how to change the map to a graph and then how to answer the question for a graph. [Suggested prerequisites: Introduction to Graph Theory]
Adjacency Matrices (Not yet available.)
How do we represent a graph on a computer? The most common solution to this question, adjacency matrices, is presented along with several algorithms to find a shortest path... [Suggested prerequisites: Introduction to Graph Theory]
Related Resources for these Tutorials: Other Graph Theory Resources on the Internet:
Chris Caldwell caldwell@utm.edu