Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that we had a set of vertices labelled $1,2,\ldots,n$.

There will several ways to connect vertices using edges. Assume that the graph is simple and connected.

In what efficient (or if there is no efficient way, you can just tell me whatever procedure you can think of) way do we be able to calculate the number of possible ways the graph can be made? (even if some graphs are isomorphic to each other, they are counted as separate cases.)

share|improve this question
    
I don't understand what "no subgraph of a graph is at least connected to one of other subgraphs". –  Arturo Magidin Jun 7 '12 at 2:33
    
Do you allow loops (edges with the same vertex at both ends)? Do you allow more than one edge between two vertices? Finally, can you explain the parenthetical comment in the second paragraph? It’s not clear as it stands. –  Brian M. Scott Jun 7 '12 at 2:34
    
If you are talking about simple connected graphs, then the sequence is A001349 in the On-line encyclopedia of integer sequences. There is no formula given, but there are references for computing the numbers. –  Arturo Magidin Jun 7 '12 at 2:35
    
@ArturoMagidin yes, I am talking about simple connected graphs. –  Shoeinger Veronica Jun 7 '12 at 2:40
    
@ShoeingerVeronica: That's called a "connected" graph. "Simple" means there are no multiple edges between the same two vertices and no loops. So you are talking about the sequence I refered to; there are citations to articles about how to count the number, presumably as efficiently as is known. –  Arturo Magidin Jun 7 '12 at 2:40

4 Answers 4

up vote 5 down vote accepted

There are $\binom{n}2=\frac12n(n-1)$ pairs of distinct points. If you do not allow loops or multiple edges, each of these pairs determines one possible edge, and you can have any subset of those possible edges. A set with $\binom{n}2$ members has $2^{\binom{n}2}$ subsets, so there are $2^{\binom{n}2}$ possible graphs without loops or multiple edges.

If you demand that the graphs be connected, the problem becomes very much harder. From your final comment I take it that you are in effect counting labelled graphs. This sequence of numbers is A001187 in the On-Line Encyclopedia of Integer Sequences. If $d_n$ is the number of labelled, connected, simple graphs on $n$ vertices, the numbers $d_n$ satisfy the recurrence

$$\sum_k\binom{n}kkd_k2^{\binom{n-k}2}=n\binom{n}k\;,$$

from which it’s possible to calculate $d_n$ for small values of $n$. This recurrence is derived as formula (3.10.2) in Herbert S. Wilf, generatingfunctionology, 2nd edition, which is available for free download here.

According to MathWorld, Brendan McKay’s software package nauty includes a routine that efficiently enumerates such graphs; it’s available here.

If you count unlabelled graphs instead, so that you don’t count isomorphic graphs separately, you get the sequence mentioned by Arturo in the comments.

share|improve this answer

As I indicated in the comment, this is sequence A001349 in the On-Line Encyclopedia of Integer Sequences. There is no closed formula listed, but there are a couple of references to computer calculations and algorithms. I suggest that's the place where you want to start.

share|improve this answer

IF it is a simple, connected graph, then for the set of vertices {v: v exists in V}, v is adjacent to every other vertex in V. This type of graph is denoted Kn. For Kn, there will be n vertices and (n(n-1))/2 edges.

To determine how many subsets of edges a Kn graph will produce, consider the powerset as Brian M. Scott stated in a previous comment. If S is a finite set with n elements, then the powerset of S will have 2^n elements where n is the number of elements in the set S.

Assuming that the n in Kn is any non-negative integer, then shouldn't the set be considered countably infinite? If so, this would make the cardinality of the powerset Alepha 0.

share|improve this answer
    
Please use the right math formatting, see e.g. here. –  Glen The Udderboat Apr 8 '13 at 8:07

You can use exponential generating functions for this. The exponential generating functions $C(x)$ for connected labeled graphs and $D(x)$ for all labeled graphs are related by

$$D(x)=\mathrm e^{C(x)-1}\;,$$

which you can show using the decomposition of a labeled graph into its connected components.

As others have noted, we have

$$ D(x)=\sum_{n=0}^\infty\frac{2^{n(n-1)/2}}{n!}x^n\;, $$

so

$$ \begin{align} C(x) &= 1+\log\sum_{n=0}^\infty\frac{2^{n(n-1)/2}}{n!}x^n \\ &= 1+\log\left(1+x+\frac2{2!}x^2+\frac8{3!}x^3+\frac{64}{4!}x^4+\dotso\right) \\ &= 1+x+\frac1{2!}x^2+\frac4{3!}x^3+\frac{38}{4!}x^4+\dotso \;. \end{align} $$

Thus there are $1,1,1,4,38,\dotsc$ different connected graphs on $0,1,2,3,4,\dotsc$ labeled vertices.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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