I want to calculate the number of connected graphs with n vertices. There is no other constraints like loop etc.

I am unable to think a general method for the same.

Any help appreciated.

[EDIT] I am looking something on lines of a general formula using combinatorics rather than the counting approach.

[EDIT 2] Restating the question: I want to calculate the number of connected graphs with n vertices.

  • $\begingroup$ What do you mean with "no constraints like loop"? Loops are not allowed? Or loops are not excluded? $\endgroup$ – Hagen von Eitzen Apr 3 '13 at 14:59
  • $\begingroup$ Related. $\endgroup$ – Cameron Buie Apr 3 '13 at 15:07
  • $\begingroup$ @Hegen As I said "no other constraints like loop" i.e. graphs with loops are to be included. $\endgroup$ – Aman Deep Gautam Apr 3 '13 at 15:11
  • 1
    $\begingroup$ Included?! Then there's an infinite number of non-isomorphic (connected) graphs on 1 vertex: For any $k \geq 0$, add $k$ loops to the vertex. Are you adding a restriction that there's at most one loop on each vertex? Also, are the graphs labelled or unlabelled? The difference between labelled and unlabelled totally changes graphical enumeration questions. May I suggest adding a table of what graphs are counted for $n \in \{1,2,3\}$ to your question? It might be easier to understand what you're asking then. $\endgroup$ – Douglas S. Stones Apr 3 '13 at 15:45
  • $\begingroup$ @DouglasS.Stones I think what I edited for clarification is creating doubts. Please see the edit. I think it should be clear now what I want to do. $\endgroup$ – Aman Deep Gautam Apr 3 '13 at 16:32

See enumerations at OEIS or at MathWorld Connected Graph.


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.