ABSTRACT
A traversal is a way of visiting (traversing) every desired place. For example, a traversal of a house would be a path that goes to every room. We are concerned with graph traversals (because we are studying graph theory). Sometimes we want to traverse every edge of a graph exactly once, but we don’t mind visiting some vertices multiple times. This is called an Euler traversal. Sometimes we want to traverse every vertex of a graph exactly once (in which case we cannot traverse any edge more than once). This is called a Hamilton traversal. For each sort of traversal, we call it a circuit if we need to end up back where we started, and a trail or path otherwise. We are going to develop conditions on a graph that tell us when it has an Euler circuit or trail. There are almost no useful conditions on a graph that tell us when it has a Hamilton circuit or path! This is related to a very practical problem called the Traveling Salesperson Problem (TSP for short)—the problem is for the traveling salesperson to visit all the cities in an area to sell stuff and to find the shortest route to save on fuel. Le sigh; there is no good general solution. Strangely enough, there is a nice way to find the shortest route between any two particular points, and so we will learn about that.
