patternMinor
Undirected graph with exponential number of simple cycles
Viewed 0 times
numbersimplegraphwithexponentialundirectedcycles
Problem
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.
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.
Solution
The graph below contains $3m+1$ vertices and at least $2^m$ simple cycles (illustration has $m=3$):
Context
StackExchange Computer Science Q#101241, answer score: 5
Revisions (0)
No revisions yet.