What's number of connected graphs on $m$ vertices (unlabeled) and $n$ edges ? For example $m = 5$ and $n = 5$ , the answer is $5$ . When the $m$ and $n$ become greater , it's not possible to draw all graphs . I'm curious about the general formula .

  • $\begingroup$ Have a look at this sequence. $\endgroup$ – Jens Sep 10 '17 at 12:37
  • $\begingroup$ @Jens Thanks , can you explain that because I'm not familiar with OEIS ? $\endgroup$ – S.H.W Sep 10 '17 at 13:17
  • $\begingroup$ Look at the example in the link. First row is for $n=1$, $k=0$. Second row is for $n=2$, $k=0, 1$. Third row is for $n=3$, $k=0, 1, 2, 3$. You can find your own example in the fifth row, where for $k=5$ the answer is $5$. $\endgroup$ – Jens Sep 10 '17 at 13:28
  • $\begingroup$ you may find an answer in [How many connected graphs V vertices and E edges] $\endgroup$ – Shubhrajit Bhattacharya Sep 10 '17 at 14:06
  • $\begingroup$ This problem was also discussed at the following MSE link. $\endgroup$ – Marko Riedel Sep 10 '17 at 23:13

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.