Given $n$ vertices, the question is to answer how many different connected graphs exist?

For example, $f(1)=1,f(2)=1,f(3)=2,f(4)=6 \cdots$.

Here I exclude the isomorphic graphs.

I know there is a sequence http://oeis.org/A001349

But can anyone try to explain how to calculate the sequence?

  • 1
    $\begingroup$ Are you looking for a closed formula? $\endgroup$ – TheHolyJoker Jan 17 '20 at 19:51
  • 1
    $\begingroup$ The link to the oeis entry contains several references that should answer your question. $\endgroup$ – Morgan Rodgers Jan 17 '20 at 19:58
  • $\begingroup$ @TheHolyJoker Yes, is there a closed formula? $\endgroup$ – Kimmi Jan 17 '20 at 20:17
  • 2
    $\begingroup$ The OEIS sequence A000088 "Number of onnected graphs with n nodes" has formulas and computer code. The sequences A000088 and A001349 are connected by the Euler transform. $\endgroup$ – Somos Jan 17 '20 at 20:47
  • 1
    $\begingroup$ This MSE link may prove useful. $\endgroup$ – Marko Riedel Jan 18 '20 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.