GODF's blog

Counting Graphs with Cycle
By GODF, 5 years 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

»
5 years 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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply