# Undirected graph with exponential number of simple cycles

Hey I am new to graph theory and this question has me stuck for hours.

What is an example of undirected graph with n nodes where the number of simple cycles is exponential in n.

I was looking at complete graphs, but here's the catch: the total number of edges should be in theta of n.

Please help! I need to prove the correctness of such a graph but I can't find an example of the graph in the first place.

The Möbius ladder $$M_{2n}$$, also called pizza graph, which has $$2n$$ vertices and $$3n$$ edges, have $$2^n+n^2-n+1$$ simple cycles. Here $$n\ge3$$.

The following two views of the Möbius ladder $$M_{16}$$ is also taken from the same Wikipedia entry. Be careful that the central point on the pizza view is not a vertex of the graph. Here is an animation showing the transformation between the two views.

Exercise 1. (easy) Show there are at least $$2^{n-1}$$ simple cycles in $$M_{2n}$$.

Exercise 2. Show there are $$2^n+n^2-n+1$$ simple cycles in $$M_{2n}$$.

The graph below contains $$3m+1$$ vertices and at least $$2^m$$ simple cycles (illustration has $$m=3$$):

Any time you need to make an exponential number of things out of a linear number of parts, you should think "subsets": a set of size $$k$$ has $$2^k$$ subsets. In this case, the approach is to find a structure where you have a linear-sized set of choices and each subset of those choices leads to a different cycle.

In Yuval's example, you have a linear number of diamonds and, in each one, you can choose any subset of "left" vertices from the diamonds and put those in your cycle, giving exponentially many options.

In Apass.Jack's example, if you start going clockwise around the outside, you can use any odd-cardinality subset of the the radial edges to move back and forth between the outside and inside before arriving back at your start position. (If you uncrossed the two edges at the top, you'd need an even-cardinality subset of radial edges, instead.)