This week’s post gives a complete solution to the problem can you draw this shape without lifting your pencil? Occupy Math presents a classroom activity that uses graph theory and originates in Russia, long ago, with the Seven Bridges of Königsberg, an after-dinner game.
Many line drawings can be traced without lifting your pencil, many cannot.
The picture above shows how the mathematician Leonhard Euler diagrammed the game. There are four pieces of land A, B, C, and D and seven bridges a, b, c, d, f, and g. After dinner, citizens of the city would try to find a way to cross the seven bridges once each, ending up where they started. Euler did not help the reputation of mathematicians as fun guys: he proved that there simply wasn’t a solution. It turns out that his method of spoiling everyone’s after-dinner fun was exactly what was needed to figure out if you can (or can’t) draw a shape without lifting your pencil.
The basic reasoning is simple. When you enter and then leave a given piece of land, you use up two bridges. To leave and return to your starting point you also use two bridges. That means that the number of bridges touching each piece of land must be even. From Euler’s diagram, above, it is easy to see that the number of bridges are odd (A has 5, B has 3, C has 3, D has 3) so, in a way, it could not be worse. To see that this kind of thinking solves the “can I draw this?” question, think of the strolling citizens as pencil points. The land masses are places where lines come together and the bridges are the lines you are trying to draw.
Both the pictures above are impossible by Euler’s criterion. The blue image on the right is hopeless – six different places where lines come together, each with three lines. Odd, odd, odd, odd, odd, odd! The figure on the left with two red dots, though, is possible if you don’t insist on getting back to where you started. If there is a place you leave but don’t come back to, it can tolerate an odd number of lines. Likewise, if you didn’t leave from the place you end up, that point can have an odd number of lines too.
You can draw a shape if the number of lines meeting at a point is always even or odd only twice. In the second case you must start and end at the odd points.
Notice that there are corners on the left drawing where two lines come together. Two is even, so there is no problem, but you can look at points where two lines meet as places you just pass through. Here is an example of a shape you can draw – and return to start – that uses curved lines.
You can use this as a discovery activity or pretend to have magic powers. Or both.
Euler’s criterion – all even or only two odd numbers of lines at meeting places – is something that you can check with a glance for simple shapes. Occupy Math worked up an activity on this with twelve example shapes. You can have your students generate shapes – not too ornate – and then somehow know which ones are possible.
This activity also works pretty well as a discovery activity – give the students positive and negative examples (don’t say which are which) and tell them there is an organizing principle. The activity is to rediscover Euler’s criterion. If you are a teacher and would like to work this up with learning goals and other modern decorations, let Occupy Math know. There are several related activities – like letting first graders make their own puzzles with carpet remnants – that could be worked up.
Two historical notes. First, when Occupy Math first started using the Bridges of Königsberg as an activity, he tried to find the city in the modern world. The current name of the city is Kaliningrad. Second, the Steve Young song Seven Bridges Road (I like the Eagle’s version) has nothing to do with the seven bridges of Königsberg.
Occupy Math is part of the University of Guelph’s outreach effort. Please let him (dashlock@uoguelph.ca) know if you have outreach needs. Generating more of the can/can’t draw shapes is not hard and we have other outreach on tap. Have a good outreach or discovery activity you would like spread the word on? Comment or tweet and let Occupy Math know.
I hope to see you here again,
Daniel Ashlock,
University of Guelph,
Department of Mathematics and Statistics
Occupy Math 