Blog Post 9

\(1\) \(\underline{\text{An Introduction to Graph Theory}}\) The concepts of graph theory go all the way back to the eighteenth century when, in 1736, Euler published what is believed to be the first paper on the very subject. It contained a famous problem known as the Königsberg Bridges Problem. This is a puzzle which considers the question of whether or not a person, starting from their home, could pass over each of the seven bridges that crossed the Pregal River exactly once before returning home. Euler was able to reconstruct the problem in such a way that allowed for him to lay the foundation of graph theory. To solve the puzzle, Euler replaced the land masses with vertices and let edges represent the bridges. The mathematical structure that became of his work is now called a graph.

To begin, we define a graph as a collection of vertices (points) that are connected by edges (lines). One fundamental question that arises when we talk about graphs is: Can the graph be drawn without lifting your pencil off the paper and without overlapping of the lines? You might recall that such a question is asked in connection to the elementary school problem using the following graph:

At such an age, one would experiment with this problem until the solution is reached. In particular, note that one such way to draw the graph would be \(3\) \(\rightarrow\) \(4\) \(\rightarrow\) \(5\) \(\rightarrow\) \(1\) \(\rightarrow\) \(2\) \(\rightarrow\) \(3\) \(\rightarrow\) \(6\) \(\rightarrow\) \(5\) \(\rightarrow\) \(2\) \(\rightarrow\) \(6\) \(\rightarrow\) \(4\). If a solution can be found, we say that the graph is drawable.