On Monday, Auguest 9th, we'll delve into Math Modeling and its impact on the real world! We'll be taking an every day problem and use our math modeling skills to address it. See you there!

View the Presentation Here

View the Problem Here

Learn About Math Modeling Here

What is the Königsberg Bridge Problem?

The Königsberg bridge problem takes place in the city of Königsberg, in medieval Germany. There are 7 bridges which connect the different parts of the city (figure 1). Carl Gottleib Ehler, a mathematician, posed the question- is it possible to cross each bridge once and use all 7 of them? He grew so frustrated with the problem that he sent for help from Leonard Euler, one of the greatest mathematicians of the time. The answer? You can't. Euler found that the problem couldn't be answered by conventional mathematics, so he discovered Graph Theory to compensate. In graph theory, each of the land masses in the problem (the island, north, south, and west sections of the city) can be represented as a node, with each of the bridges representing connections between them (called "edges" in mathematics) (Figure 2). In order to go from one land mass to another and back, you'd need the number of bridges to be multiples of 2, or even. Because the number of bridges, or edges in the Königsberg problem are all odd, you wouldn't be able to form a complete path, or "Euler path". But, what if you could? Would it be possible to remove a bridge, or add one, or change the parameters of the problem in order to make it possible? Explore this on your own, email us your solution or any questions, and have fun with this! We'll be exploring Graph Theory and this problem in more depth during Launch II, and will address a problem of our own as well! question further!

What is Graph Theory?

As a result of the Königsberg problem, Euler discovered Graph Theory. In math, Graph Theory is the study of shapes, or more accurately, networks. Networks are composed of points or vertices, and edges connecting them. In the bridge problem, each vertex would represent a part of the city (North, South, Island, and East), and the edges connecting them would represent the bridges, as seen below. It simplifies the picture a lot more, doesn't it?

Now, try to find one route that uses each bridge only once. This is called an Eulean path. Can you make an Eulean circuit, or a path that starts and ends at the same vertex? If you play around with this, you'll find that it's impossible. Now, try adding or taking out bridges to see if that would make it possible to construct a Euluean path. What about a Eulean circuit? See if you can see if there are any patterns to what allows a certain graph to have a Eulean path or Eulean circuit. Try out the figures below, too!

If you keep prodding at the problem, you'll notice that networks with all even degrees, or number of edges, allow a network to form a Eulean circuit. Networks that have vertices at odd degrees don't allow Eluean circuits, or even Eulean paths. Lastly, you need at least one vertex with an even degree in a given network to ensure that you have a Eulean path. Why is this true? What are some other rules you can find? Even more important, how can these rules (theorems) help us in the real world?

Helpful Resources

About Graph Theory, About the Königsberg Bridge Problem, Koningsberg, The TED Version

Slide Deck Citations

We'll update this section soon!

Glossary

We'll update this section soon!

• Graph Theory: The study of networks, comprised of vertices (points) and edges (connecting lines).
• Network: A shape made up of vertices and edges.
• Edge: A line connecting two vertices.
• Vertex: A point representing the origin of connections between two abstract things.