New York City is a scary place for anyone. Even most born and bred new Yorkers get terrified when they don’t know how to go somewhere. Being that person standing on the street holding a map is just calling for unnecessary attention. I've lived in New York my whole life, and I must admit that no matter how lost I may be, I will never pull out a map on the streets. New Yorkers are mean people (excluding myself obviously), and when you try to ask someone for directions, it’s rare that you are going to be lucky enough to find someone who actually wants to stop and help you. Have you ever tried using the subway? Are you aware of all the different lines and how many of them overlap and which ones are only going express on that day? It’s an exhausting process. Recently, I read an article on two individuals who wanted to break the Guinness World Record and ride the subway to every single station in New York that it would go to. As I read more about their journey, I was intrigued as to how they found all the mathematical background information and what paths they used. I started thinking to myself that as a New York resident, I really didn’t know that much about the subway other than the few stops that I myself have visited most frequently. This made me question whether there were routes that visited all the boroughs and which route would be able to reach every borough in the shortest amount of time.
In order to figure out a logical way of maneuvering the New York City subway system, it is necessary to first understand a little background information on graph theory and different types of paths that can occur. “In mathematics and computer science, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.” (Wikipedia, Graph Theory) Every graph has different aspects that make it unique, however, a graph in this context “is made up of vertices or nodes and lines called edges that connect them.” A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another.” (Wikipedia, Graph Theory) For the purposes of looking at the subway system, there are multiple different routing graph options that someone could take in attempting to find a suitable route. These methods would entail using theories based on the Hamiltonian path problem, the shortest path problem, or even Euler’s path problem.
Back in Mathematical Modeling, a course taken by many of the seniors during our sophomore year, Dr. Nabel (reference Dr. Nabel) introduced us to the topic of Hamiltonian paths. “Hamiltonian graphs are named after Sir William Hamilton, an Irish mathematician (1805-1865), who invented a puzzle, called the Icosian game, which he sold for 25 guineas to a games manufacturer in Dublin. The puzzle involved a dodecahedron on which each of the 20 vertices was labeled by the name of some capital city in the world. The object of the game was to construct, using the edges of the dodecahedron, a tour of all the cities which visited each city exactly once, beginning and ending at the same city. In other words, one had essentially to form a Hamiltonian cycle in the graph corresponding to the dodecahedron.” (A First Look at Graph Theory, page 100) Knowing a little background about how the Hamiltonian graphs, the actual definition of Hamiltonian path is “a graph G with a path which contains every vertex of G.” (A First Look at Graph Theory, page 99) This would imply that I am looking for a route which contains every subway station on the route that I am taking. In order to have a Hamiltonian cycle, there would first need to be a Hamiltonian path in the graph. A graph G will be Hamiltonian “if and only if its underlying simple graph is Hamiltonian since if G is Hamiltonian then any Hamiltonian cycle in G will remain a Hamiltonian cycle in the underlying simple graph of G.” (A First Look at Graph Theory, page