MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a simple cubic graph with $n$ vertices (which implies that $n$ is even), what is a good upper bound on the number of cycles of length $n/2$ it can have?

A random cubic graph has $\Theta((4/3)^n/n)$ cycles of length $n/2$, if I did my sums right. So do random cubic bipartite graphs. Also the whole cycle space has size $2^{n/2+1}$, so twice that is a (silly) upper bound.

Where's the truth?

ADDED: Counts for n=4,6,...,24: 0,2,6,12,20,20,48,48,132,118,312 (not in OEIS). All these are unique except that for 20 vertices there are two graphs.

share|cite|improve this question
How about (3n/2) choose (n/2)? Another silly bound, but it might lead somewhere. You could also divide the graph into connected groups of 5 edges and note that a cycle can intersect each group of edges in only 8 ways. (I assume each group is acyclic, perhaps a bad move.) Gerhard "Spins Me Round Right Round" Paseman, 2013.10.03 – Gerhard Paseman Oct 3 '13 at 18:16
Interesting question! I communicated it to Michael Krivelevich. He does not know, but suggests that the methods from might be useful – Boris Bukh Oct 3 '13 at 18:20
The related integer sequence appears to be $4,12,24,40,40,96,96$ – Jernej Oct 3 '13 at 23:21
@Jernej: Agreed if you count oriented cycles. I'm posting counts for unoriented cycles. – Brendan McKay Oct 4 '13 at 2:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.