A graph has 29 vertices and 41 edges. What is the minimum number of distinct cycles that this graph could have?

Question

I am trying to solve this. However, it is not clear for me the best way to model the problem.

I was trying to start with a star graph, with 29 vertices, 28 edges and no cycle. Slowly, I would add an edge to build one cycle. Slowly, my star graph would approach to a wheel graph.

This is a picture of what I am calling a star graph.

Are start graphs turning to wheel graphs the best way to minimize cycles creation?

If yes, What am I doing wrong? If no, how to solve the problem?

Thanks.

Answer 1

Starting with a star graph is a good approach. When you make the star you have $28$ arms and $13$ edges yet to place. You can place the $13$ on disjoint pairs and argue that you have only made $13$ cycles. The answers to the question vadim123 linked show this is a minimum so you are done. Your approach works as long as the number of edges is less than $1+\frac 32(v-1)$ where $v$ is the number of vertices.