<p>It is not $O(n)$ unless $k=3$. For $k$ even, the maximum length of a cycle in the complete bipartite graph $K_{n,k/2}$ is $k$, and the number of length-$k$ cycles is $(\frac{k}{2}-1)! n^{k/2}=\Theta(n^{k/2})$. For instance, $K_{2,n}$ has a quadratic number of 4-cycles, but no cycles longer than 4.</p>

<p>On the other hand, for any constant bound $k$ on the length of the longest cycle, the number of triangles really is $O(n)$. Here's a quick proof: in a depth first search tree, each edge goes from the lower of its two endpoints to an ancestor at most $k-1$ steps back, so any leaf of the tree has degree at most $k-1$ and belongs to at most $\binom{k-1}{2}$ triangles. Now remove the leaf and induct.</p>

CC BY-SA 3.0
2014-02-04T07:28:35.803Z
yes, you are right :)
virgi
CC BY-SA 3.0
2014-02-03T23:34:54.277Z
2014-02-04T07:42:55.123Z
2014-02-04T07:42:55.123Z
David Eppstein
<p>I wrote a short clingo program to check the small values (it can quickly handle graphs of up to 7 vertices.  Beyond that, the grounding can take quite a while):</p>

<p>I got this table</p>

<pre><code>                            n (vertices)
                         3   4   5   6   7

                      3  1   1   2   2   3

                      4      3   3   6  10

k (cycle length)      5         12  12  12

                      6             60  60

                      7                360
</code></pre>

<p>Here's the program:</p>

<pre><code>num(1..n).
is_sym_order(empty,0).
ncontains(empty,K) :- num(K).
is_sym_order(cons(K,empty),1) :- num(K).
last(cons(K,empty), K) :- num(K).
is_sym_order(cons(K,S),M+1) :- is_sym_order(S,M), ncontains(S,K), last(S,L), K &gt; L.
ncontains(cons(K,S), J) :- J != K, ncontains(S,J), is_sym_order(cons(K,S),_).
last(cons(K,S), L) :- last(S,L), is_sym_order(cons(K,S),_).
sec_last(cons(A,S),A) :- is_sym_order(cons(A,S),2).
sec_last(cons(K,S), SL) :- sec_last(S,SL), is_sym_order(cons(K,S),_).
is_sub_order(cons(A,S), M) :- A &gt; SL, sec_last(S,SL), is_sym_order(cons(A,S), M).

vertex(1..n).
{is_edge(V,W)} :- vertex(V), vertex(W), V &lt; W.
sym_edge(V,W;W,V) :- is_edge(V,W).

is_path(cons(V,empty)) :- vertex(V).

is_path(cons(A,cons(B,S))) :- is_path(cons(B,S)), sym_edge(A,B), is_sym_order(cons(A,cons(B,S)),_).
is_cycle(cons(A,S)) :- is_path(cons(A,S)), is_edge(V,A), last(S,V), is_sub_order(cons(A,S),M), M &gt;= k.

:- is_cycle(S), is_sub_order(S,M), M &gt; k.
prim_cycle(S) :- is_cycle(S), is_sub_order(S,k).
:~ not is_cycle(S), is_sub_order(S,k).[1,S]

num_cycs(C) :- C = #count{is_cycle(S):is_cycle(S)}.
#show is_edge/2.
#show num_cycs/1.
#show prim_cycle/1.
</code></pre>

CC BY-SA 3.0
2014-02-03T19:40:13.827Z
2014-02-03T19:40:13.827Z
dspyz
<p>How many cycles $C_k$ $(k \geq 3)$ are there in a $n $ vertex graph such that graph doesn't have any cycle $C_m$ $(m&gt;k)$.</p>

<p>For example $n=5$, $k=3$, then graph will have at most two $C_3$'s so that $G$ will not have any $C_k (k &gt; 3).$  </p>

<p>I am thinking that there are $O(n)$ cycles will be there satisfying above conditions.</p>

<p>Can some one help me out.</p>

CC BY-SA 3.0
2013-09-27T10:29:28.753Z
are you talking about vertex-induced cycles? disjoint cycles?
Igor Shinkar
CC BY-SA 3.0
2013-09-27T10:32:46.783Z
The answer may depend on the parity of $m-k$. For example, consider a balanced blow-up of a 5-cycle. This graph contains no 6-cycles, but it contains $\Theta(n^5)$ induced 5-cycles.
Igor Shinkar
CC BY-SA 3.0
2013-09-27T12:07:40.340Z
@IgorShinkar I read the question as "what is the maximum number of $k$-cycles in an $n$-vertex graph that has no $m$-cycle for any $m > k$?" so $m$ is not a parameter, it's universally quantified
Sasho Nikolov
CC BY-SA 3.0
2013-09-28T07:56:32.653Z
I assume you're talking about induced cycles (holes).  If you want the minimum number, it's surely 0, an empty graph.  If you want the maximum number, it is n^3 for k=3 (consider a complete graph).
Yixin Cao
CC BY-SA 3.0
2013-09-29T06:23:21.510Z
@YixinCao For k=3, If you consider a complete graph with 'n' vertices then we will have cycle whose length is more than 3.
I am looking for maximum number cycles of length k in a graph such that graph shouldn't contain any cycle of length more than k
Kumar
<graph-theory><graph-algorithms>
Number of cycles in a Graph
Kumar
# Number of cycles in a Graph

(Asked by: username_0 on 2013-09-27)

How many cycles $C\_k$ $(k \geq 3)$ are there in a $n $ vertex graph such that graph doesn't have any cycle $C\_m$ $(m>k)$.

For example $n=5$, $k=3$, then graph will have at most two $C\_3$'s so that $G$ will not have any $C\_k (k > 3).$

I am thinking that there are $O(n)$ cycles will be there satisfying above conditions.

Can some one help me out.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: are you talking about vertex-induced cycles? disjoint cycles?  
> **username_1**: The answer may depend on the parity of $m-k$. For example, consider a balanced blow-up of a 5-cycle. This graph contains no 6-cycles, but it contains $\Theta(n^5)$ induced 5-cycles.  
> **username_2**: @IgorShinkar I read the question as "what is the maximum number of $k$-cycles in an $n$-vertex graph that has no $m$-cycle for any $m > k$?" so $m$ is not a parameter, it's universally quantified  
> **username_3**: I assume you're talking about induced cycles (holes).  If you want the minimum number, it's surely 0, an empty graph.  If you want the maximum number, it is n^3 for k=3 (consider a complete graph).  
> **username_0**: @YixinCao For k=3, If you consider a complete graph with 'n' vertices then we will have cycle whose length is more than 3. I am looking for maximum number cycles of length k in a graph such that graph shouldn't contain any cycle of length more than k  

---

## 2 answers

### Answer by username_4 on 2014-02-03. Score: 5 | Accepted answer

It is not $O(n)$ unless $k=3$. For $k$ even, the maximum length of a cycle in the complete bipartite graph $K\_{n,k/2}$ is $k$, and the number of length-$k$ cycles is $(\frac{k}{2}-1)! n^{k/2}=\Theta(n^{k/2})$. For instance, $K\_{2,n}$ has a quadratic number of 4-cycles, but no cycles longer than 4.

On the other hand, for any constant bound $k$ on the length of the longest cycle, the number of triangles really is $O(n)$. Here's a quick proof: in a depth first search tree, each edge goes from the lower of its two endpoints to an ancestor at most $k-1$ steps back, so any leaf of the tree has degree at most $k-1$ and belongs to at most $\binom{k-1}{2}$ triangles. Now remove the leaf and induct.

> **Comments:**
> **username_5**: yes, you are right :)  

---

### Answer by username_6 on 2014-02-03. Score: 1

I wrote a short clingo program to check the small values (it can quickly handle graphs of up to 7 vertices.  Beyond that, the grounding can take quite a while):
I got this table
                            n (vertices)
                         3   4   5   6   7

                      3  1   1   2   2   3

                      4      3   3   6  10

k (cycle length)      5         12  12  12

                      6             60  60

                      7                360

Here's the program:
num(1..n).
is_sym_order(empty,0).
ncontains(empty,K) :- num(K).
is_sym_order(cons(K,empty),1) :- num(K).
last(cons(K,empty), K) :- num(K).
is_sym_order(cons(K,S),M+1) :- is_sym_order(S,M), ncontains(S,K), last(S,L), K > L.
ncontains(cons(K,S), J) :- J != K, ncontains(S,J), is_sym_order(cons(K,S),_).
last(cons(K,S), L) :- last(S,L), is_sym_order(cons(K,S),_).
sec_last(cons(A,S),A) :- is_sym_order(cons(A,S),2).
sec_last(cons(K,S), SL) :- sec_last(S,SL), is_sym_order(cons(K,S),_).
is_sub_order(cons(A,S), M) :- A > SL, sec_last(S,SL), is_sym_order(cons(A,S), M).

vertex(1..n).
{is_edge(V,W)} :- vertex(V), vertex(W), V < W.
sym_edge(V,W;W,V) :- is_edge(V,W).

is_path(cons(V,empty)) :- vertex(V).

is_path(cons(A,cons(B,S))) :- is_path(cons(B,S)), sym_edge(A,B), is_sym_order(cons(A,cons(B,S)),_).
is_cycle(cons(A,S)) :- is_path(cons(A,S)), is_edge(V,A), last(S,V), is_sub_order(cons(A,S),M), M >= k.

:- is_cycle(S), is_sub_order(S,M), M > k.
prim_cycle(S) :- is_cycle(S), is_sub_order(S,k).
:~ not is_cycle(S), is_sub_order(S,k).[1,S]

num_cycs(C) :- C = #count{is_cycle(S):is_cycle(S)}.
#show is_edge/2.
#show num_cycs/1.
#show prim_cycle/1.


---

