$(1)\:$How many non-isomorphic connected simple graphs are there with $n$ vertices when n is,
$(2)\:$Draw all non-isomorphic, cycle free, connected graphs having six vertices.

For $(1)$ when $n=4$, it's only $6$ case I got. But when it is $5$, I was unable to find out $21$ case. Actually I found $15$ case and here is my question arrive,

Is there any prediction without drawing all of those case$?$ If not then how could someone ensure his/her answer in Exam $(\text{For big enough n})?$

For $(2)$ I have the same situation.
I was thinking there should be other way to predict the answer of this kind question. Any help will be appreciated.
Thanks in advances.

  • $\begingroup$ The following MSE link on non-isomorphic connected graphs might prove useful. $\endgroup$ – Marko Riedel Dec 30 '19 at 23:17
  • $\begingroup$ Seems like induction on the maximum degree of a vertex ought to go a long way in the cycle-free case. If $n=4$, I can only find two connected cycle-free graphs. $\endgroup$ – Robert Shore Dec 30 '19 at 23:25
  • 2
    $\begingroup$ @MarkoRiedel It seems to understand your answer$(\text{Linked})$ I need many stuff to study. But at that time it will be best if I have a generating function/recurrence relation to get my desire answer. Can you provide any$?$ And thanks for your response I will definitely read your answer$(\text{Linked})$ after exam. $\endgroup$ – NajmunNahar Dec 31 '19 at 7:10
  • $\begingroup$ @MarkoRiedel Any OEIS sequence which can tell for $n=1,\cdots,10?$ $\endgroup$ – Dr.Antidode Dec 31 '19 at 9:11
  • $\begingroup$ oeis but there does not seem to be any generating function of formula. $\endgroup$ – almagest Dec 31 '19 at 11:33

I tried for $(2)$ and got $6$ case$(\text{Sorry for my poor drawing})$, enter image description here
I think the main hack will be to find all possible tree.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.