We Used New York City's 47 Bridges To Solve An 18th Century Math Puzzle

The George Washington Bridge isn't the only way to get from one landmass to another in New York City.

NYC is built on an archipelago, and consequently has a ton of bridges. There are 47 non-rail-only bridges in New York City that appear on Wikipedia's list of said bridges.

In this exercise, we answer: is it possible to get around NYC by crossing every bridge just once?

This is more than just a fun math puzzle. The process for answering this question eventually led to modern-day, real-world applications that couldn't have been imagined when a similar question was first posed nearly 300 years ago.

The Seven Bridges Of Koenigsburg

One of the greatest mathematicians of all time, Leonhard Euler, once solved an interesting mathematical puzzle.

The city of Koenigsburg in the 17th and 18th centuries was built at a fork in a river, and seven bridges connected the banks of the river to each other and to an island in the middle. Euler came up with an elegant answer to the deceptively simple question of whether or not it was possible to walk over each of the seven bridges exactly one time each.

Euler was able to show, using a line of reasoning explored below, that this was not possible - the way the bridges were configured, such a walk could not exist.

The 47ish Bridges Of NYC

Business Insider is headquartered in a city that also has a number of bridges, and so we were curious as to whether a tour of the bridges of New York City, going over each bridge exactly once, was possible.

New York is built on an archipelago, and consequently has a ton of bridges. There are 47 non-rail-only bridges in New York City that appear on Wikipedia's list of said bridges. This map shows those bridges that are readily available in the city government's publicly available map of all city streets:

We will not have to worry about all of these bridges. There are a lot of small bridges covering waterways entirely contained in some landmass - the tiny red dots in western Brooklyn going over the Gowanus Canal, or the handful of bridges over Newtown Creek on the border between Brooklyn and Queens.

These small, in-landmass bridges, traversing an inlet or a creek surrounded by land, are trivial in our analysis of whether or not it is possible to go over every bridge in New York. We can walk or drive over all of these bridges exactly once by default: go across one bridge over Newtown Creek, walk around the creek, and then go over the next bridge:

Since we can walk around these in-landmass waterways in this fashion, we just need to concern ourselves with bridges between distinct landmasses. We include in this set of bridges the Marine Parkway-Gil Hodges Memorial bridge connecting southeastern Brooklyn to Rockaway Peninsula, even though the latter is connected to the former by land, since we would prefer to not have to leave the city and go into Nassau County in our bridge tour. Here are the 27 inter-landmass bridges:

There is a lot going on in the Harlem River between Manhattan and the Bronx, so here is a closeup of that area:

We run into an immediate problem for our goal of crossing every bridge exactly once. There are a handful of islands that are connected by only one bridge - Staten Island in the southwest, Roosevelt Island in the East River, Riker's Island prison just north of Queens, and City Island to the east of the Bronx. These bridges are in blue in the next map:

These bridges are automatically going to be a problem for us, and make it impossible to cross every bridge in the city. If we do not start on, say, Staten Island, we will at some point have to cross the Verrazano-Narrows Bridge, and then we will be stuck on Staten Island. If we do start on Staten Island, we can leave the island, but then at some point we will have to cross to Roosevelt Island, and similarly be stuck there.

So, unfortunately, because of these single bridge island cases, we are out of luck, and the bridges of New York are untourable. However, we can turn to the more modest problem of only looking at bridges between landmasses with two or more bridges connecting them by removing the problem cases. So, with all due respect to the good people of Staten, Roosevelt, and City Islands, and the not quite as good people of Riker's Island, we will be leaving these sites and their isolated bridges behind, leaving us with the following map:

The 23 Bridges Of NYC

Although this problem is more modest in scope, as we are no longer looking at every bridge in New York, it is a little trickier. With our original map, we were able to quickly determine that going over every bridge exactly once is impossible by just looking at those four single-bridge islands. Here, it's a bit harder to tell glancing at our new map whether or not our tour over the remaining 23 bridges is possible.

All that mattered for these relatively isolated islands is the number of bridges connected to them - the actual size or location of the island, or which landmass the island connects to, or how long the bridge was, or how far the bridge was from other bridges on another landmass, did not change anything. The problem was just that these islands had one bridge going out of them.

For the remaining landmasses and bridges, this pattern continues. The only thing that will be relevant in figuring out whether we can take a tour of these bridges is the number of bridges connected to each landmass.

The key is seeing that for most of our landmasses, we need an even number of bridges connected to that landmass. Except in the cases of our starting location and our ending location, if we cross a bridge to get to an area, we will have to later leave that area by another bridge. Since our intermediate landmasses need to have their bridges come in pairs - one bridge to enter the landmass, and one bridge to leave the landmass - they will need to have an even number of bridges connected to each of them.

This gives us a pretty simple criterion to see whether or not it is possible for any configuration of landmasses and bridges to take a walk over each bridge exactly once: we need to have at most two landmasses with an odd number of bridges leading to each of them, and every other landmass needs an even number of bridges leading to it.

This realization was at the heart of Euler's solution to the original Bridges of Koenigsburg problem. In Koenigsburg, each of the four relevant landmasses was connected to an odd number of bridges, making a bridge tour impossible.

In these terms, we can see why our relatively isolated islands gave us so much trouble. Here we had four landmasses that had an odd number - one - of bridges connected to them.

So, for each of our non-isolated landmasses, we can count up the number of bridges connected to each landmass, and see if we satisfy our criterion. We start in the northern half of the city:

Manhattan has 16 bridges leading out of it, the Bronx is attached to 13 bridges, and Wards Island has a total of 4 connections to other locations. Now we look at our southern landmasses:

Brooklyn and Queens together have 9 bridges, and the Rockaways and Broad Channel Island have 2 bridges each.

So, our bridge counting criterion is satisfied. Four of our six landmasses - Manhattan, Wards Island, the Rockaways, and Broad Channel Island - all have an even number of bridges coming into and out of them. These will be the intermediate landmasses in our tour. Only two of the landmasses - the Bronx and Brooklyn/Queens - have an odd number of bridges connected. These will be our starting and ending locations. We should be able to make a tour of the non-isolated bridges of New York City.

It turns out that there are a number of ways to do this. As an example of one such tour, we start in the Bronx, and zig zag back and forth across the Harlem River between the Bronx and Manhattan. Then, we take advantage of the RFK Triborough Bridge and 103rd St pedestrian bridge to cover Wards Island, and then head through Queens to hit the two bridges linking eastern Queens and the Bronx:

To finish our tour, we head south overland through Queens, take the Jamaica Bay bridges, and then finish up with the Queensboro Bridge and the three bridges linking Brooklyn and Manhattan:

So, it is in fact possible, with the exception of the single-bridge islands, to go over each of the bridges in New York City exactly once.

Why Does This Matter?

This particular puzzle is, at a glance, mostly just a fun observation, whose only application is for particularly fastidious marathon runners. However, it holds an important place in the history of mathematics. Euler's writings on the Bridges of Koenigsburg problem represented some of the first work in what would become the modern mathematical areas of topology and graph theory.

Topology is the study of those geometric properties of shapes and spaces that do not rely strictly on exact distances. The problem of finding a path covering all the bridges in a city exactly once is a topological problem - the distances between bridges, the sizes of the different landmasses, and the exact positioning of the bridges do not matter. The only thing we need to know about a city is how the landmasses are connected to each other by bridges, a topological concern.

This problem can also be expressed in terms of modern graph theory, and Euler's solution to the problem resembles the techniques used in this subject today. Graph theory describes systems where we have some collection of objects, usually represented as points or "vertices", in which pairs of objects may or may not be connected to each other, with connections represented by lines or "edges" between the points.

Graph theory is enormously useful in studying networks. Power grids, computer networks, and relationships between people on social networking sites, to give just a few examples, can all be modeled by different types of graphs, and results from graph theory are essential to understanding and managing these complex systems.

The bridge problem can be easily expressed as an abstract graph: our vertex points are the islands and landmasses in our city, and for each bridge between two landmasses, we place a linear edge between the corresponding vertices. Our question then becomes whether or not we can find a path through this graph that goes through each edge exactly once, and our solution is that this is possible only if at most two vertices are connected to an odd number of edges. While Euler did not frame the problem using exactly this more modern terminology, his idea of analyzing a graph by considering things like the number of edges connected to a particular vertex is a fundamental part of graph theory.