Graph Theory has been around for hundreds of years and now has many applications that help people solve problems from pecking chickens to delivering your mail. It all started with a simple problem. The Prussian people of Konigsberg Germany wanted to know if they could cross every one of the city’s seven bridges once and only once and end up back where they had started. When Leonhard Euler in the 1700’s visited the city he was intrigued by the problem (Legner, 2015). Euler chose to look at this problem with a whole new perspective. Instead of thinking of the bridges as a path, he focused on the four land masses that the bridges connected. Using a dot for each of the land masses, he connected each of these using lines to represent the bridges. Now the problem could be viewed as tracing the lines of the graph without lifting your pencil (Rhishikesh, 2015).. While proving that it was not possible for a person to cross all seven bridges once in a walk, Euler’s ideas created graph theory. He also proved that in order for a multigraph to have, what was dubbed an Euler Path, there had to be no more than two odd vertices.
At first, graphs like Euler’s just became another fun problem to solve. Rowan Hamilton created such a puzzle and sold it for twenty pounds. This puzzle involved a dodecahedron, finding a path that passes through every vertex only once, and ending where you started. Unlike Euler’s circuits this remains an open problem and we do not know all the necessary or sufficient conditions that are needed for a Hamiltonian circuit to exist for a particular graph. In the 19th century these graphs began to be used for practical purposes like Chemistry. James Sylvester used graphs with dots to represent different atoms and the connecting lines for chemical bonds (Carson, 2013).
Now graphs are being studied to find the optimal path between points depending on certain conditions. This helps with moving people, packages, and data and has led to solutions like the Voronoi assignment models or linear programming. Even the internet can be seen as one huge graph with every page as a vertex and the links as edges connecting it all together. Facebook can be considered a big social graph that connects the whole world(Legner, 2015). Could you find a Hamiltonian path connecting every person through Facebook? With the age of computers there is no limits to what graph theory could accomplish.