Tourism
If you can copy a network without lifting your pen off the paper and without drawing any line twice, then it is traversable. Decide which of these diagrams are traversable.
Problem
If you can copy a network
- without lifting your pen off the paper
- without drawing any line twice
then it is traversable.
Decide which of these diagrams are traversable.
If you end up where you started when you draw a traversable diagram it is called a traversing circuit.
If you don't end up where you started when you draw a traversable diagram it is called a traversing path.
Can you give a set of criteria for determining whether a diagram is traversable by a path or a circuit or neither?
A related problem?
If you make a chain with all 28 dominoes so that adjacent ends of dominoes match, and it has 5 spots at one end, how many spots will it have at the other end? And if it has a different number of spots at one end?
Can you explain your results?
If you haven't got dominoes, you may find our Dominoes Environment useful.
Getting Started
Have a look at the nodes (the points where the lines meet).
Student Solutions
We received a number of good responses to this problem.
Eva from Benenden School and Georgina both worked out that the traversable diagrams are: 1, 2, 3, 7, 8, 9, 11.
An anonymous contributor explained that:
"The rule to find whether a network is traversable or not is by looking at points called nodes.
Nodes are places where two or more lines meet. On these networks, the nodes are clearly shown by the black points in the diagrams.
Now you are probably wondering what this has to do with the network being traversable or not.
The node either would have an odd or even number of lines connected to it. Do not count the nodes with an even number of lines connected to it. Count the number of nodes with an odd number of lines connected to it.
If there are no odd nodes or if there are two odd nodes, that means that the network it traversable.
Networks with only two odd nodes are in a traversable path and networks with no odd nodes are in a traversable circuit."
Georgina added that:
"If a node has an even number of lines coming from it, this means that your pen will be able to both enter and leave that node. If not, the pen must start or finish at the node. As you can start and finish at only twonodes (start at one, finish at the other) any network with more than 2 odd nodes is not traversable.
If there are no odd nodes this means that the network can be drawn without taking your pen off the paper, starting and finishing at the same place."
Sarah from Colyton (and Andrei from School No. 205 in Bucharest) noticed that:
"For Curcuits:
Every point must have an even number of lines coming out of it."
Jonathan and Thomas from Heversham St Peters Primary School and Amy from Farlingaye High School listed their results as follows:
"1 is a traversable path
2 is a traversable circuit
3 is a traversable circuit
4 is not traversable
5 is not traversable
6 is not traversable
7 is a traversable circuit
8 is a traversable path
9 is a traversable circuit
10 is not traversable
11 is a traversable path"
Yanqing from LCC School summarised her findings as follows:
"Look at the nodes: if the node has an even number of lines coming from it, we call it an even node; if it has an odd number of lines, call it an odd node. If the network has NO odd nodes (all even nodes), it is a traversable circuit; if the network has 2 odd nodes, it is a traversable path; if the network has more than 2 odd nodes, it is not traversable."
Thank you all for your solutions.
Teachers' Resources
Why do this problem?
This problem offers a great opportunity for students to explore particular cases and move towards generalisations and develop their geometric reasoning. By exploring each of the given networks to see if they are traversable as a circuit or a path or neither, students may start to notice features of the networks. If students record their results, they can start to look for patterns across the full set of networks and start to generalise and make conjectures.
Possible approach
You could start by sharing the full set of networks and asking students to see if they can find a route round the network that goes over each line once, but without taking their pen off the paper. At this point you could introduce the language of traversable, traversing path and traversing circuit.
Alternatively, you could show three of the networks, e.g. 6, 7, 8 and just ask students to work on these initially and then move on to others. This may help to focus discussion.
Encourage students to actually trace over or draw out the networks, rather than just trying to visualise routes round them, because they might notice different features of the networks from physically drawing or tracing them.
Once students have had a chance to explore the networks, encourage them to record their findings, perhaps in a table. At this stage students have probably been focusing on whether the graphs are traversable, but you could suggest leaving an extra row or column to record anything else they have noticed about the different networks or that comes up in discussion.
Bring the class together to share findings, and discuss anything they have noticed, which might include some conjectures as they start to generalise. As well as saying whether the different graphs are traversable, and as a circuit or a path, students may mention ideas such as "networks 2 and 3 seem similar" and "the networks that are not traversable have lots of points with three lines meet". Depending on students' contributions, it might be helpful to draw attention to the number of lines that meet at points on the different networks. This may help students to work towards finding criteria for a graph to be traversable by a path, circuit or neither.
If students have started counting the number of lines that meet at the different points in the networks, they may notice that some of the non-traversable networks have several points where three lines meet, whereas the traversable ones have none or two. It could be helpful for these students to spend a bit of time thinking about routes through points where three lines lines meet, to help them make sense of the more general idea, which is that having an odd number of lines meeting at points is an important feature for these graphs.
Key questions
Which graphs are traversable? Does it matter which point you start at?
How many lines meet at each of the points?
What do the non-traversable graphs have in common?
What do the traversable graphs have in common? What about traversing circuits, or traversing paths?
What happens if you add a line here, or here, or ... ?
Possible support
Encourage students to start working with just one or two networks (they don't have to attempt the given ones in order). If they can't initially find a traversing path or traversing circuit, ask them to try another route or another starting point. This way, they may start to work systematically and notice what features of the network is preventing it from being traversable.
Possible extension
Once students have made conjectures about criteria, invite them to alter the given networks or draw new ones that they predict are traversable by a path, circuit or neither. They can test each other's networks and predictions and work towards explaining why these criteria determine the result.
As a further challenge, ask students about the dominoes problem. Can they use the ideas from their work with the networks to help them tackle the dominoes problem?