You may also like

Magic W Wrap Up

Prove that you cannot form a Magic W with a total of 12 or less or with a with a total of 18 or more.

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.

Tree Graphs

A connected graph is a graph in which we can get from any vertex to any other by travelling along the edges. A tree is a connected graph with no closed circuits (or loops. Prove that every tree has exactly one more vertex than it has edges.

Simply Graphs

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:
  • 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 came up with a few other categories of our own.
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?