Description

How many distinct "loops" are there in a certain graph? Can we find every distinct graph with a fixed number of loops? Here we have almost all the graphs with four distinct loops. The arrows leaving each graph indicate the type of graph obtained by shrinking one of its edges.

Given a graph, it is a fun exercise to figure out how many distinct "loops" are present in the graph. A loop in a graph is a path starting and ending at the same vertex, and we don't want to consider a loop "new" if it can be made from previously identified loops. On the other hand, a more challenging exercise is to fix a number and find every distinct graph which has that number of loops. Here we have almost all of the graphs with four distinct loops such that every vertex has at least 3 incident edges. The only such graphs we are missing are the ones with an edge whose removal results in a disconnected graph. Can you start at the top row, choose edges to shrink, and make your way to four petaled rose on the bottom row? Can you find a four loop graph missing from the image?