A Tour of Minnesota

Could you visit every county in Minnesota by land without having to pass back through a county you've already visited?

Such a journey is known as an Eulerian path, or Eulerian trail.

A related question might be: can you make such a trip and end up in the county in which you started? This would be an example of an Eulerian cycle.

Both these ideas borrow the name of Leonhard Euler, an 18^th-century mathematician famous for, among many other things, his contributions to graph theory. Graph theory is the study of graphs, which can be summarized as networks of vertices (sometimes called nodes in computer science) and the connections between them, called edges.

If we represent Minnesota as a graph where each county is a vertex, and relate their adjacency by drawing edges between them, we can answer these questions while sitting on our couch.

The Ground Rules

First, let's set the ground rules:

1. We can only travel on the ground. No airplane rides to skip over counties.
2. We must stay within Minnesota. We can't use the Dakotas, Canada, Wisconsin, or Iowa to bypass Minnesota counties.
3. We count two counties adjacent if they share a border at any point, ignoring notions of trespassing or the existence of roads. Whether counties that meet at a corner are adjacent is an interesting question. We will examine this later.

An Eulerian Cycle

We'll first consider the question of there being a cycle, meaning a trip that takes us back to our starting point.

Euler proved a theorem that states a simple test for this property:

A connected graph has an Euler cycle if and only if every vertex has an even number of incident edges.

The first matter to determine is if Minnesota is indeed a connected graph.

In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

A graph is said to be connected if every pair of vertices in the graph is connected.

In other words, if I pick any two counties in the state, can I travel from one to the other? Yes, but there are two notable quasi-islands:

1. Cook County in northeast Minnesota is adjacent to only Lake County. A single adjacency is sufficient this vertex to be connected.
2. Lake of the Woods County has a region which has a land border only with Canada, but most of the county is contiguous with the rest of Minnesota. As we could walk from land in Lake of the Woods to Beltrami county, this satisfies the condition for connectivity.

At this point, we've already answered the question about the existence of an Eulerian cycle - that answer is no. Cook County has a single neighbor, making it a vertex with an odd number of edges. If we start outside of Cook County, and enter Cook County, we won't have any way to leave without retracing our steps. Similarly, if we start in Cook County, we can't return without retracing our steps.

An Eulerian Trail

Next, let's examine the test for the existence of an Eulerian trail, where we visit every county but do not necessarily return to our starting point.

An undirected graph has an Eulerian trail if and only if exactly zero or two vertices have odd degree, and all of its vertices with non-zero degree belong to a single connected component.

"Degree" in this context refers to the number of edges connected to a vertex. Or in simpler terms: the number of neighbors a vertex has.

Minnesota satisfies the last criterion, as we already established that its counties represent a connected graph.

A brief examination of a map answers the other question:

• We already know Cook County has an odd degree (it has one neighbor).
• Wabasha county in the southeast indisputably has three neighbors (Goodhue, Olmstead, Winona).
• Carlton county also has three (Aitkin, Pine, Saint Louis).

There are many more counties with odd degree (forty, by my count), but since we know we have at least three, Minnesota fails the test of only having either zero or two.

Adjusting the Rules

Now, what if we adjusted our definition of adjacent? Let's say we redefine the word to exclude counties that meet only at a point, such as Pope, Stevens, Grant, and Douglas counties, which all meet at a single corner.

This doesn't change our answer - while the number of counties with even and odd neighbor counts changes under this new definition, we know we still have three (Cook, Wabasha, and Carlton) that clearly have an odd degree.

What if we adjusted the other rules, such as allowing travel outside of the state? Perhaps that will be the subject of another post!

Pack the Car!

So, while visiting every county of the great state of Minnesota might be a wonderful travel idea, we won't be able to do it in a purely Eulerian style. We'll have to retrace our steps at some point - computing a minimally retraced path would be interesting - but perhaps that's not such a bad itinerary. Let's not let graph theory get in the way of a fun road trip.