Leonhard Euler
was a famous Swiss mathematician, physicist,
astronomer, geographer, logician, and engineer.
In the time of Euler, in the town of Konigsberg in Prussia,
there was a river containing two islands.
The islands were connected to the banks of the river
by seven bridges as shown below.
Again, we have the river,
we have the two islands, and the seven bridges.
People would spend time walking over the bridges
for exercise.
As time passed, a question arose.
Was it possible to plan a walk
so that you cross each bridge once and only once?
This is a graph theory question.
Euler was able to determine that it was not possible.
Graph theory is a relatively new area of mathematics,
first studied by Euler in 1735.
Since then, it has blossomed into a powerful tool
used in nearly every branch of science
and is currently an active area of mathematics research.
The Seven Bridges of Konigsberg
is the problem that originally inspired graph theory.
Consider a different problem:
Below is a graph of four dots connected to some lines
as shown here on the left.
Is it possible to trace out each line once and only once,
without lifting up your pencil,
starting and ending on a dot?
One such possible attempt might look something like this,
starting here at the bottom,
one,
two,
three,
four,
five,
six,
and notice here, the only option is to retrace a line,
and therefore this is an unsuccessful attempt.
So you may want to pause the video
and see if you can come up with a successful attempt.
There's an obvious connection between this problem
and the Seven Bridges of Konigsberg problem.
Any path in the dot and line drawing
corresponds exactly to a path
over the bridges of Konigsberg.
Looking at the image of the bridges of Konigsberg,
notice how I placed four dots on the four land masses.
From here, if I draw lines connecting the dots
passing over the bridges,
the two graphs are equivalent.
And now let's talk about some definitions.
Pictures like the dot and line drawings are called graphs.
Graphs are made up of a collection of dots called vertices
and lines connecting those dots called edges.
Looking at the graph here on the right,
again we have a set of vertices and a set of edges.
Vertex is singular for vertices.
When two vertices are connected,
we say they are adjacent.
So for example, this vertex and this vertex are adjacent
as well as this vertex and this vertex,
and so on.
The nice thing about looking at graphs
instead of pictures of rivers, islands, and bridges
is that we now have a mathematical object to study.
We have distilled the important parts of the bridge picture
for the purposes of the problem.
A walk is a sequence of vertices
such that consecutive vertices are adjacent.
A walk in which no edges repeated is called a trail,
and a trail in which no vertex is repeated is called a path.
A walk which uses each edge exactly once
is called an Euler path,
and Euler path which starts and stops at the same vertex
is an Euler circuit.
The degree of a vertex
is a number of edges connected to a vertex
or emanating from a vertex.
So for example, this vertex here on the right
has degree three
because three edges emanate from this vertex.
This vertex here in the middle has degree five
because there are five edges emanating from the vertex.
A graph is connected
if you can get from any vertex to any other vertex
by following some path of edges.
The graph above is connected.
A graph that is not connected
can be thought of as two separate graphs
drawn close together.
And finally, a graph which can be drawn,
in the plane, without any edges crossing is called planar.
They provided graph is planar.
And now let's look at an example.
Use the following graphs below,
is there an Euler path?
Is there an Euler circuit?
A walk which uses each edge exactly once is an Euler path.
So starting here at the bottom,
let's see if we have an Euler path.
So we're going to start here
and we ended here.
We were able to form a walk
which uses each edge exactly once,
and therefore the graph does have an Euler path.
However, we did not start and stop at the same vertex,
we do not have an Euler circuit.
And now let's look at the second graph,
and again we're going to start down here again.
Let's follow a way, similar walk.
Notice, this time we started and ended at the same vertex
and we did use each edge exactly once.
This graph has an Euler path
as well as an Euler circuit.
And now let's look at some other uses of graphs.
Al, Bob, Cam, Dan, and Euler
are all members of a social networking website.
The site allows members to be friends with each other.
It turns out that Al and Cam are friends,
as our Bob and Dan.
Euler is friends with everyone.
Represent the situation with a graph.
Each person will be represented by a vertex
and each friendship will be represented by an edge.
That is, two vertices will be adjacent
if and only if the people represented by those vertices
are friends.
To get started, let's just list five vertices in a row
and label them A, B, C, D, and E
for Al, Bob, Cam, Dan, and Euler.
From here, since Al and Cam are friends,
we need an edge from A to C,
Bob and Dan are friends,
we need an edge from B to D,
Euler is friends with everyone,
we need an edge from E to D,
E to C, E to B, and E to A.
This graph does represent the given situation,
but it might be easier to read if we represent the graph
in this form here on the right.
These two graphs are equivalent
because we have the same vertices and the same edges
but notice how this one's much neater.
And for our last example,
three houses must be connected to each of three utilities.
What is the possible graph for this situation?
Well, a possible graph is provided here below.
We have the three homes, H1, H2, H3,
and we have the three utilities, U1, U2, and U3.
Notice how there's an edge from each house
to each of the three utilities.
The next question is, is it possible to do this
without any utility poles crossing?
Remember, if we can, then the graph is planar,
if we can't, then it's not planar.
Let's try one attempt.
Here are the three edges
connecting House 1 to the three utilities,
and here are three edges connecting House 2
to the three utilities.
Notice so far, no edges cross,
and now we need to try to connect House 3
to the three utilities.
So here we can connect House 3 to Utility 3.
We can also connect House 3 to Utility 1 here,
but notice now I'm stuck.
I can't connect House 3 to Utility 2
without crossing an edge.
So from this attempt, the graph is not planar
but that doesn't mean this is the only attempt.
So you may want to pause the video and see
if you can form a graph
to verify whether the given graph on the left
is planar or not.
I hope you found this helpful.