HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Undirected graph with exponential number of simple cycles

Submitted by: @import:stackexchange-cs··
0
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.

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.