What is the maximun possible number of simple cycles in an undirected connected garph with n nodes and n+1 edges?

94 Views Asked by At

Considering we have an undirected connected graph with n nodes and n+1 edges , what is the maximum number of simple cycles the graph can have ? what is the proof ?

1

There are 1 best solutions below

2
On

Remove two edges while keeping the graph connected. A connected graph with $n$ nodes and $n-1$ edges is a tree (hence without cycles). Add one of the edges, back, and you create one cycle. Add the other edge back, and you create at most $2$ more simple cycles, so the total is at most three.