GODF's blog

By GODF, 20 months ago, In English

Hi. In this comment, there is a formula to count the number of graphs with i vertices having cycle length j. Which is  Can somebody explain the formula ?. I understand that first part. We choose j vertices from i vertices to form a cycle. Then we permute them. which is j!. But I could not figure out the rest.

Thank you for your time in advance.

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's derived fairly straightforwardly from Cayley's formula. They even mention that in the thread. Basically, graphs which have exactly one cycle have trees branching out of the cycle; you can see the connection from there.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for answer. Why should we divide by 2 ?