Give Now  »

Noon Edition

How To Find The Shortest Route: Leonhard Euler And Euler Circuits

If you ever had a paper route or any other job that took you through a series of streets, you may have spent some time working out the quickest way to complete the circuit.

Fastest Route

In order to cover your route most efficiently, you would want to avoid going back over streets you had already covered and you would want to avoid traveling on streets that were not part of your route.

Child's Play

Children play a game in which one child draws a simple, geometric design on a piece of paper. The other then tries to trace the design with a pencil. The rules are that you can't take the pencil off the paper and you can't go over the same line twice.

The catch is that not all designs can be traced this way. As you worked out the most efficient paper route, you might have tried this same exercise on a street map of the neighborhood you had to cover.

Leonhard Euler And Traceable Routes

In the 1700's the Swiss-born mathematician, Leonhard Euler worked out a way to tell whether or not a particular design was traceable in this way simply by counting the number of lines at each intersection in the design.

He found that if all the intersections had an even number of lines coming into them, then you could start at any point in the design and trace the whole thing without lifting your pen or going over any line twice.

Euler Circuits

Today, a design that meets these requirements is called an Euler circuit after the eighteenth-century mathematician. So, if you're planning a paper route, you might want to figure out whether the streets you've been given make up an Euler circuit.

Once again, count the number of roads coming in to each intersection. If all intersections have an even number of roads, then you're in luck.

Support For Indiana Public Media Comes From

About A Moment of Science