Eulerian and Hamiltonian Graphs

Graph theory is an area of mathematics that has found many applications in a variety of disciplines. Throughout this text, we will encounter a number of them. However, graph theory traces its origins to a problem in Königsberg, Prussia (now Kaliningrad, Russia) nearly three centuries ago. The river Pregel passes through the city, and there are two large islands in the middle of the channel. These islands were connected to the mainland by seven bridges as indicated in . It is said that the citizens of Königsberg often wondered if it was possible for one to leave his home, walk through the city in such a way that he crossed each bridge precisely one time, and end up at home again. Leonhard Euler settled this problem in 1736 by using graph theory in the form of .

Let \(\bfG\) be a graph without isolated vertices. We say that \(\bfG\) is eulerian provided that there is a sequence \((x_0,x_1,x_2,\dots,x_t)\) of vertices from \(\bfG\), with repetition allowed, so that

1. \(x_0=x_t\)
2. \(i=0,1,\dots, t-1\)\(x_ix_{i+1}\)\(\bfG\)
3. \(e\in E\)\(i\)\(0\le i\lt t\)\(e=x_ix_{i+1}\)

When \(\bfG\) is eulerian, a sequence satisfying these three conditions is called an eulerian circuit. A sequence of vertices \((x_0,x_1,\dots,x_t)\) is called a circuit when it satisfies only the first two of these conditions. Note that a sequence consisting of a single vertex is a circuit. Before proceeding to Euler's elegant characterization of eulerian graphs, let's use SageMath to generate some graphs that are and are not eulerian.

Run the code below. It will execute until it finds a graph \(\bfG\) that is eulerian. The output that will be produced is a list of the degrees of the vertices of the graph \(\bfG\) followed by a drawing of \(\bfG\).

We encourage you to evaluate the run the code above multiple times, even changing the number of vertices and edges. If it seems to be running a log time, it may be that you have made the number of edges too small, so try increasing it a bit. Do you notice anything about the degrees of the vertices in the graphs produced?

Now let's try to find a graph \(\bfH\) that is not eulerian. Again, the output is the list of degrees of \(\bfH\) followed by a drawing of \(\bfH\).

One thing you probably noticed in running this second block of code is that it tended to come back much faster than the first. That would suggest that the non-eulerian graphs outnumber the eulerian graphs. Did you notice anything different about the degrees of the vertices in these graphs compared to the ones that were eulerian?

The following elementary theorem completely characterizes eulerian graphs. Its proof gives an algorithm that is easily implemented.

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.