The right connections

It’s almost the exciting time of year when campus is flooded with newly-admitted high school seniors and their families, eager to take their first look around at Duke. This also presents an interesting challenge to current students: how do we show our new Blue Devils around campus without walking by the same locations several times? Walking the same paths in different directions not only makes for a boring tour, but is also a terribly inefficient use of our time as students. With a little foresight and the right mathematics, however, this problem can be avoided.

The mathematician Leonhard Euler spent much of his life in the city of Konigsberg, Prussia, (now Kaliningrad, Russia). During his lifetime the city center of Konigsberg was set on both sides of the Pregel River, and seven bridges had been built to connect both banks of the river to each other and to two islands in the middle of the Pregel. Euler, being the analytical sort that he was, one day wondered whether it was possible to plan a walk through the city that crossed each bridge once and only once. Crossing the river without using a bridge was impractical, and for Euler’s purposes crossing a bridge only partially and then turning back was unacceptable.

Euler struggled with the problem for some time, but his solution laid the foundations of modern graph theory and topology. He first abstracted the city and its bridges into four distinct locations: The north and south banks and each island were reduced to mathematical objects called “nodes.” Connecting the nodes, Euler drew seven lines or “edges,” each representing a different bridge. Euler’s simplification of the problem relied on his genius observation that the actual geography of the city wasn’t relevant to the question—only the pattern of connections (i.e. bridges) made a difference.

He then reasoned that whenever one walks onto a landmass via a bridge, one must also leave by a bridge, possibly excluding the first and last stops on the walk. In other words, at most two nodes can have an odd number of edges, and the rest must have an even number of edges. In modern parlance, the number of edges touching a node is called the degree of that node.

Sadly for Euler, all four nodes in his graph had a degree of either three or five - so his ideal walk through Konigsberg was impossible. In homage to him, modern graph theory defines a graph traversal that uses each edge exactly once an “Eulerian path.” A special case of an Eulerian path is an Eulerian circuit, which uses each edge exactly once and also ends up back in the same place it began. For a circuit to be possible all nodes must have an even degree.

Planning the perfect tour of West Campus can be approached in the same way. Konigsberg’s land masses can be replaced by Duke’s landmarks; major walkways substitute for bridges. In a few minutes I was able to plan a tour that visits the Duke Chapel and Gardens, Perkins Library, the Engineering Quad, the Bryan Center, West Union, Krzyzewskiville and Keohane Quad, which both starts and ends at the Undergraduate Admissions Office. Since every “bridge” is used exactly once, by the end of the tour you’ll have seen nearly all of West Campus without boring your guest with the same views over and over.

Before you are inevitably tasked with showing a new student or family member around campus, I hope you’ll take the time to make sure your tour is mathematically optimal. Feel free to add or remove any destinations and see if an Eulerian circuit is still possible. For extra credit, try planning a route that only uses wheelchair accessible paths, avoids street traffic, or complies with other constraints. Armed with basic graph theory, you’ll be able to identify the impossible scenarios right away and focus on the more promising ones.

Aside from planning campus tours, graph theory has a multitude of practical applications. Many kinds of complex networks have been represented as graphs by the scientists who study them. Communication, data organization, internet links, relationships (in real life and on social media), the migrations of animals and the construction of linguistic syntax have all been studied through the lens of graph theory. Euler’s insights provide the basic framework for most of the mathematical formalisms behind the study of networks.