Graphs and Graph Theory – an Introduction - Learning Neo4j - page 2

In this topic, we will be working with a completely different type of subject—the
graphs that you might know from your math classes. I, for once, distinctly remember
being taught the basics of discrete Mathematics in one of my university classes, and I
alsorememberindingitterriblycomplexanddificulttoworkwith.LittledidIknow
that my later professional career will use these techniques in a software context, let
alone that I would be writing a topic on this topic.
So,whataregraphs?Toexplainthis,Ithinkitis useful to put a little historic context
around the concept. Graphs are actually quite old as a concept. They were invented, or
atleastirstdescribed,inanacademicpaperbythewell-knownSwissmathematician
Leonhard Euler. He was trying to solve an age-old problem that we now know as the 7
bridges of Königsberg . The problem at hand was pretty simple to understand.
Königsberg has a beautiful medieval city in the Prussian empire, situated on the river
Pregel. It is located between Poland and Lithuania in today's Russia. If you try to
lookituponanymodern-daymap,youwillmostlikelynotinditasitiscurrently
known as Kaliningrad. The Pregel not only cut Königsberg into a left- and right-
bank side of the city, but it also created an island in the middle of the river, which
was known as the Kneiphof. The result of this peculiar situation was a city that was
cut into four parts. We will refer to them as A, B, C and D, which were connected by
seven bridges (labeled a, b, c, d, e, f, and g in the following diagram).This gives us
the following situation:
• The seven bridges are connected to the four different parts of the city
• The essence of the problem that people were trying to solve was to take a
tour of the city, visiting every one of its parts and crossing every single
one of its bridges, without having to walk a single bridge or street twice
In the following diagram, you can see how Euler illustrated this problem in his
original 1736 paper:
Illustration of the mentioned problem as mentioned by Euler in his paper in 1736