Main Data History
Show Index Toggle 0 comments
  •  Quick Edit
  • 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.

    Some other basic information that should be covered in regard to the fundamentals of graph theory are the ideas of the vertex set and the edge set. While they may be self-explanatory, the vertex set of the graph is a set of all vertices of the graph and the edge set is the set of all edges. If we consider the graph pictured above, we define the vertex set as \(V=\{1,2,3,4,5,6\}\) and the edge set as \(E=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{1,5\},\{2,5\},\{2,6\},\{5,6\},\{3,6\},\{4,6\}\}\).

    Furthermore, two vertices are adjacent if an edge exists between them. The number of vertices adjacent to the vertex \(v\) is called the degree of \(v\), denoted \(d(v)\). In our example, we see that \(d(6)=4\). This can come in handy in telling us whether or not a graph is drawable. A graph is not drawable if it has more than two vertices which have an odd degree. This explains why the graph in the Königsberg Bridges Problem cannot be solved. Looking back on that graph, all the vertices have a degree which is odd.