The Beginning of graph theory can be traced back to the 18th century, when mathematicians like Euler, Libniz, and Gauss were alive.
To know more about how graph theory began, watch the following podcast. The script is posted below the following video podcast, so you can follow along if you wish.
Here is the PowerPoint used in the video podcast and the script if you would like to follow along.
Cue Chopin's "Nocturne in E Flat Major (Op. 9 No.2)".
This is a short podcast about the history of Graph Theory, specifically we are going to talk a little bit about how Graph Theory got started; how it all began. Switch to slide 2 of PowerPoint.
Before we talk about how graph theory got started, we should define what graph theory is. Bring in first two bullet points of slide 2 of PowerPoint.
Graph theory is defined as the mathematical structures of abstract relationships between objects
(Andersen, 2011)
. Bring in last two bullet points of slide 2 of PowerPoint.
Of if you would like a more formal definition, it is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph
in the context of graph theory is made up of vertices, nodes, or points which are connected by edges, arcs, or lines
(“Introduction to Graph Theory”, 2016)
.
This is why the notation for Graph Theory is written as capital g is equal to the ordered pair v comma e, where v represents the vertices of the graph, and e
represents the edges of the graph (G=(V,E)) . Switch to slide 3 of PowerPoint.
Now that we have sufficiently defined what graph theory is, we can talk about how it got started. The beginning of it all. The following quote does a good job of
summarizing how it all began. Read quote.
"The origins of graph theory are humble, even frivolous. Whereas many branches of mathematics were motivated by fundamental problems of calculation,
motion, and measurement, the problems which led to the development of graph theory were often little more than puzzles, designed to test the ingenuity
rather than to stimulate the imagination. But despite the apparent triviality of such puzzles, they captured the interest of mathematicians, with the
result that graph theory has become a subject rich in theoretical results of a surprising variety and depth
(Biggs, Lloyd, & Wilson, 1976)
."
Thus, we see that graph theory began from inquiring minds interested in puzzles. I for one find puzzles, especially logic puzzles fascinating. It's
interesting to know that that interest in puzzles and finding solutions to puzzles is what began graph theory. Switch to slide 4 of PowerPoint.
Two puzzles or problems that really started graph theory are the Knight's Tour problem and the Königsberg (pronounced: Kyon-ings-burg)
Bridges problem.
Euler wrote papers solving each of these problems, the only problem is that due to lack of good record keeping, we don't know which paper was written first. Thus,
the question, which problem came first. It's important because one of these two problems started graph theory
(Alexanderson, 2006)
.
Most mathematicians accept that the Königsberg Bridges problem was the beginning
(Prakash, 2018)
. Switch to slide 5 of PowerPoint.
Now we are going to talk a little bit about each of these two problems.
Let's start with the Knight's tour problem. Bring in first two bullet points on slide 5 of PowerPoint.
To understand the problem, first let's look at how a knight's tour is defined.
A knight's tour is defined as: the knight is place on the first block of an empty board and, moving according to the rules of chess, must visit each
square exactly once. The problem is to find a path such that the knight's tour is complete. In other words, so that the knight touches every square
(“The Knight's tour problem”, 2018)
. Bring in gif on slide 5 of PowerPoint.
Here is an example of a knight's tour on a 5x5 board. Bring in bullet point #3 on slide 5 of PowerPoint.
Euler used an 8x8 square chess board, but any size can be used. Even irregularly shaped or non-square boards have been used. Bring in last bullet point on slide 5 of PowerPoint.
One thing that we should note about knight's tours is that they can either be open or closed tours. They are open tours if the ending square is only one move away
from the very first or beginning square. Otherwise it is considered closed. Bring in gif caption on slide 5 of PowerPoint.
The graphic here is an open knight's tour on a 5x5 grid. Notice how the last square is only one move away from the very first square. Switch to slide 6 of PowerPoint.
The Königsberg bridges problem needs a little bit of background before we pose the problem Bring in bullet point #1 and graphic on slide 6 of PowerPoint.
Königsberg, which is now the city of Kaliningrad in Russia consists of four islands connected by seven bridges. Here is a graphic to show what it looks like.
The first picture is the one Euler used in his proof. The second is a more simplified version that we use to visualize what the city looked like, and the third one
is how modern graph theorists would draw or visualize the city. Bring in bullet point #2 on slide 6 of PowerPoint.
Now, the problem, which is posed as a question. Can a person devise a path through the city so that they only cross each of the seven bridges once and return home
(Alexanderson, 2006)
? Bring in last bullet point on slide 6 of PowerPoint.
As I briefly mentioned before, Euler used the first picture in his proof. He didn't use the same methods as modern graph theorists, he used logic in his proof. Switch to slide 7 of PowerPoint.
To summarize, graph theory became a subject of interest because it was a way to solve puzzles, or problem long thought to be impossible, but it would also develop to be
able to model real-life behaviors.
It's an ongoing field of research and discover. So, get out there, learn some more, and get interested in research! Fade out with Chopin's "Nocturne in E Flat Major (Op. 9 No. 2)".
End presentation.