You may also like
Instant Insanity
Given the nets of 4 cubes with the faces coloured in 4 colours, build a tower so that on each vertical wall no colour is repeated, that is all 4 colours appear.
Network Trees
Explore some of the different types of network, and prove a result about network trees.
Magic Caterpillars
Label the joints and legs of these graph theory caterpillars so that the vertex sums are all equal.
Age 16 to 18
Challenge Level
Vanessa and Annie sent us this solution:
We labelled the graphs like this:
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
We grouped the graphs like this:
We noticed that graphs 7,9,10,11,12 and 13 had the same number of edges coming out of each vertex.
We also looked at which graphs you could draw without taking your pencil off the paper and without drawing the same line twice. We found out this is called traceability. Graphs 1,9,10,11,13 are traceable, starting and finishing at the same point. Graphs 2,4,6,8 are traceable, starting and finishing at different points. The other graphs are not traceable.
We checked this by counting the number of edges coming out of each vertex. If you want to start and finish at the same point, this number must be even for all the vertices in the graph. This is because every time you arrive at the vertex by one edge you need to be able to leave it by another. If you want to start and finish at different points, you need two (but only two) odd vertices. This is because the first vertex has an 'exit' edge without a corresponding 'entry' edge and vice versa for the last vertex. If you have 1 or more than 2 vertices with an odd number of edges, the graph is not traceable.
Well done! Can you think of any other interesting properties or ways to group the graphs?
We labelled the graphs like this:
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
We grouped the graphs like this:
- Graphs with loops (1 and 4) and graphs without loops (all the other graphs).
- Non-simple graphs (1,3,4) and simple graphs (all the other graphs).
- Non-connected graphs (3, 15) and connected graphs (all the other graphs).
- Trees (14,5,6) and non-trees (all the other graphs).
- Complete graphs (11,7,9) and non-complete graphs (all the other graphs)
We noticed that graphs 7,9,10,11,12 and 13 had the same number of edges coming out of each vertex.
We also looked at which graphs you could draw without taking your pencil off the paper and without drawing the same line twice. We found out this is called traceability. Graphs 1,9,10,11,13 are traceable, starting and finishing at the same point. Graphs 2,4,6,8 are traceable, starting and finishing at different points. The other graphs are not traceable.
We checked this by counting the number of edges coming out of each vertex. If you want to start and finish at the same point, this number must be even for all the vertices in the graph. This is because every time you arrive at the vertex by one edge you need to be able to leave it by another. If you want to start and finish at different points, you need two (but only two) odd vertices. This is because the first vertex has an 'exit' edge without a corresponding 'entry' edge and vice versa for the last vertex. If you have 1 or more than 2 vertices with an odd number of edges, the graph is not traceable.
Well done! Can you think of any other interesting properties or ways to group the graphs?
Copyright © 1997 - 2023. University of Cambridge.
All rights reserved.
NRICH is part of the family of activities in the Millennium Mathematics Project.
NRICH is part of the family of activities in the Millennium Mathematics Project.