3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

Two views of the Möbius ladder M16 from Wikipedia


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}$.

$\endgroup$
5
$\begingroup$

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

Graph with many cycles

$\endgroup$
3
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.