Simply Graphs

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?