Euler had a major influence on mathematics in that he developed new ideas and also extended existing ones. For example, he was the first to use e as the base of the natural logarithm, he was the first to come up with the idea of i, he developed with the power series of e… the list goes on. He made developments in a variety of mathematical areas: calculus, number theory, topology and also graph theory. Specifically, he studied and found a solution to the following problem: Is it possible to start at a point and cross over every one of the seven bridges only once and end at the starting point?
We talked about this problem in class briefly, and it is one I have studied before, but don’t remember it that well. I wanted to re-explore it and go through Euler’s solution step by step:
The first thing we do to solve this problem is to put into a different sort of map. We will represent each island by a vertex. The islands are the two areas which are surrounded by rivers. Consider the picture above. The first island is easy to find; it is directly in the middle. The second is the piece of land directly to the right of it. It is surrounded by rivers on three sides and the fourth side is basically the end of the picture; no river, no land therefore an its an island, I guess. Everything to the right of the island we will label with a vertex and the same for the left side.
So far, we have the following:
For our next step, we will draw a line between two vertices for every bridge between the two islands. There is only one bridge that goes from Island A and Island B. There are two bridges we can use to get from Island A the right side and two bridges from Island A to the left side. There is one way to get from Island B to the right side and one way to get from Island B to the left side. When we connect our island with edges, we have the following diagram:
Next, Euler looked at how many edges or bridges run into each vertex. In number theory, we call this the degree of each vertex.
So the degree of the vertex labeled “Island A” is 5 because there are five edges which are connected to this vertex or five different bridges you could cross if you were standing on Island A. Similarly, the vertex labeled “Island B” has degree 3, the vertex labeled “Right Side” has degree 3, and the vertex labeled “Left Side” has degree 3. One thing that can be noted about the number of degrees for each of the vertices is that it is odd.
We are looking for a path that starts at one vertex, goes through every edge only once and ends at the starting point. Euler called this a circuit, specifically a Euler circuit. Since every vertex has an odd degree, a Euler circuit does not exist according to Euler’s second theorem. In order for a circuit to exist, every vertex must be even.
This is because if hit a vertex, we need to come out the other side. Once we travel on an edge, we can’t travel it again because of the nature of a circuit and because of the nature of this problem; We can only cross every bridge once. So we eventually run into the problem of going to a vertex but running out of edges to take going away from the vertex. For this reason, we need an even number of degrees of in a connected graph in order to have a Euler circuit.
piforkate 