<p>If $k$ is divisible by 2 we can take a clique on $n/2$ vertices and subdivide each edge once.
This graph will have ${n/2 \choose k/2} \cdot (k/2-1)!/2$ cycles of length $k$.</p>

<p>Hence the total number of cycles is $\frac{1}{2} \sum_{i=k/2}^{i=n/2} {n/2 \choose i} \cdot (i-1)!$</p>

CC BY-SA 3.0
2014-02-12T00:43:53.607Z
2014-02-12T00:43:53.607Z
Martin Vatshelle
<p>I wish to construct an unweighted, undirected graph on $n$ nodes that maximizes the number of minimal cycles of size $\ge k$.  What is known about this problem?  How many cycles can I squeeze in?</p>

<p>Additionally, how does the problem change if I require that my graph has $\ge m$ edges?</p>

<p>Clarification: I care purely about the <em>existence</em> of a many-cycled graph; it doesn't need to be efficiently constructable.</p>

CC BY-SA 3.0
2014-02-11T11:20:35.417Z
Crossposted on [mathoverflow](http://mathoverflow.net/questions/157277/how-many-edges-can-you-put-in-a-graph-such-that-every-edge-belongs-to-a-minimal).
Marzio De Biasi
CC BY-SA 3.0
2014-02-12T00:25:58.777Z
By minimal cycle, do you mean the same as induced cycle?
Martin Vatshelle
CC BY-SA 3.0
2014-02-12T00:54:29.277Z
I see there's already an answer here, which is great. However, our policy is not to allow simultaneous cross posting (you can cross post after a day or two if you're not getting the answer you want).
Suresh Venkat
CC BY-SA 3.0
2014-02-12T04:07:48.287Z
Apologies, I won't do it again -- thanks for filling me in.
GMB
<graph-theory>
How many minimal $k$-cycles can you put in a graph?
GMB
# How many minimal $k$-cycles can you put in a graph?

(Asked by: username_0 on 2014-02-11)

I wish to construct an unweighted, undirected graph on $n$ nodes that maximizes the number of minimal cycles of size $\ge k$. What is known about this problem? How many cycles can I squeeze in?

Additionally, how does the problem change if I require that my graph has $\ge m$ edges?

Clarification: I care purely about the *existence* of a many-cycled graph; it doesn't need to be efficiently constructable.

**Tags:** graph-theory

> **Comments:**
> **username_1**: Crossposted on [mathoverflow](http://mathoverflow.net/questions/157277/how-many-edges-can-you-put-in-a-graph-such-that-every-edge-belongs-to-a-minimal).  
> **username_2**: By minimal cycle, do you mean the same as induced cycle?  
> **username_3**: I see there's already an answer here, which is great. However, our policy is not to allow simultaneous cross posting (you can cross post after a day or two if you're not getting the answer you want).  
> **username_0**: Apologies, I won't do it again -- thanks for filling me in.  

---

## 1 answers

### Answer by username_2 on 2014-02-12. Score: 2

If $k$ is divisible by 2 we can take a clique on $n/2$ vertices and subdivide each edge once.
This graph will have ${n/2 \choose k/2} \cdot (k/2-1)!/2$ cycles of length $k$.

Hence the total number of cycles is $\frac{1}{2} \sum\_{i=k/2}^{i=n/2} {n/2 \choose i} \cdot (i-1)!$


---

