Königsberg

1. In the land of Königsberg, everything is made up of one, continuous line. Here’s how to figure out if something belongs in Königsberg.

Steps:

• Click on any vertex (dot).
• To create a line, click on another vertex.
• Try to trace the whole picture by clicking on the vertices.
• You can only trace each edge (line) once.

This trace of the sailboat that started at the green dot didn’t work. Can you start at a different vertex and find a way to trace the entire sailboat?

Now try tracing the animals on the next puzzle.
Which ones belong in Königsberg?

2. The most treasured objects in Königsberg are ones that can be traced in more than one way. In fact, the more ways, the better! For the rest of the puzzles, try to answer the following questions:

a. Is it possible to trace each edge of the object once?
b. If so, mark where you start and end. Do you end where you started?
c. Can you start in the same place and end somewhere else? If so, show
how.
d. Can you start somewhere else and trace the whole object? If so, show
how.
e. Are there more than two different places where you can start? If so,
show how.

3. It’s your turn to draw some new items for the people of Königsberg. Try to draw a different item for each of the situations below or come up with your own Königsberg drawing challenge!

Draw something:

a. with 6 vertices that does not belong in Königsberg.

b. with 12 edges that does belong in Königsberg.

c. with 8 vertices that can be traced in more than two different ways.

d. with 10 vertices and 15 edges that belongs in Königsberg.

e. that does not belong in Königsberg and has the smallest possible number of vertices and edges.

f. that does not belong in Königsberg unless you remove one of its edges.

g. that does not belong in Königsberg and still won’t belong even if you remove any one of its edges.

It requires the students to think about what impossible means mathematically. There’s a difference between “I can’t do it” and “No one can do it” that students sometimes overlook.

This activity helps develop perseverance and collaboration as students who might be tempted to give up, or those satisfied with one solution, notice that others have different solutions and/or began at different starting points.

It is also a low-floor problem, in that any student can get started simply by drawing a line and connecting vertices.

For students who are ready to look for and use patterns, meaningful note-taking is instrumental in tracking what they have learned and tried so far.

Why do YOU like this activity? Try it out and let us know at info@jrmf.org!

Graphs are used to understand many types of problems, one of which is whether or not it’s possible to trace all the edges of a graph without lifting the pencil. This is called an Eulerian path and is the essential question of this activity. It comes from the famous Bridges of Königsberg problem in which Leonhard Euler proved it was impossible to cross the seven bridges in Königsberg without retracing one’s steps. This laid the foundation of graph theory which we use today to solve combinatorics problems such as city road and traffic planning or even for arranging who plays against who in round-robin tournaments.

While we may be more used to thinking of graphs as x and y coordinates on a Cartesian plane, in graph theory, a graph may refer to geometric figures consisting of points with lines connecting some of these points. The point is called a vertex and a connecting line is called an edge. We are interested in the relationship between vertices and edges and we call the number of edges that lead to a vertex the degree. Graphs for which it is possible to trace a Euler path have at most two vertices of odd degree.