MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

I need to compute the number $f(n,k)$ of graphs on $n$ vertives having a cycle of length $k$.

We can consider the graphs are labelled or not.

share|cite|improve this question
Please provide the motivation, and explain what you tried. See – Boris Bukh Feb 27 '13 at 15:37
I'm just working on the graph enumeration and I found this interesting question. Obviously there is no answer in the literature. – Pop Feb 27 '13 at 16:09
No answer in the literature? Where did you search? It is a classic problem. – Boris Bukh Feb 27 '13 at 16:37
I second Boris Bukh's comment: please provide more details, motivation, and so on. Most mathematicians don't like thinking about unmotivated and uncontextualized questions. Note that because certain graphs have extra symmetries, often exact formulas are much simpler or much more complicated (to the point of being unavailable) depending on whether you work with labeled or unlabeled graphs. It can also happen that what you care about are certain asymptotics, rather than exact formulas. So all of these concerns might be included in your question, and will guide answers. – Theo Johnson-Freyd Feb 27 '13 at 18:39
1 counts the number of triangle-free graphs on $n$ vertices, and counts the number of graphs on $n$ vertices, so the difference gives you $f(n,3)$. The links and references may or may not lead to formulas. – Gerry Myerson Feb 27 '13 at 23:21

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.