I've been thinking about this for a few days, but I haven't found a general solution yet. How many distinct simple, connected, undirected graphs are there of n labelled vertices? For example, there is one for n = 2 and there are four for n = 3. Thanks in advance!
counting simple, connected graphs
2
$\begingroup$
combinatorics
graph-theory
-
0What is a "simply connected" graph? A tree? – 2012-05-27
-
0I count three for $n=3$. – 2012-05-27
-
0@ChrisEagle I am asking for your definition, not for the number. – 2012-05-27
-
0Not necessarily a tree—it can have cycles. That's also why there are four for n=3, rather than just three. – 2012-05-27
-
1@Phira: why is my definition relevant? It's the OP we need to hear from. – 2012-05-27
-
0@Chris: So does "simply connected" just mean "connected" then? – 2012-05-27
-
0@ChrisEagle Sorry. – 2012-05-27
-
1Ach, sorry! I meant "simple, connected," not "simply connected," which I don't think is a term in graph theory. That must be the source of confusion. – 2012-05-27
-
0Rats. I thought he was asking about trees. Funny thing is, I'd been thinking of asking that exact same question. Depending on the results of this, I still might. – 2012-05-27
-
2This is [OEIS sequence A001187](http://oeis.org/A001187). When looking for this sort of sequence, it's a good idea to first search OEIS, both by text search and by determining the first few terms and searching with them. – 2012-05-27
-
0I have written an answer based on the word "labelled", but I am still unsure why the word "distinct" is used in the question. – 2012-05-27
-
0See also [this interesting question](http://math.stackexchange.com/questions/68457/number-of-connected-graphs-on-labeled-vertices-counted-according-to-parity). – 2012-05-27
-
0@Phira Thanks for the answer. Unfortunately, I'm just some kid without much of a mathematics background, so I don't quite get most of your explanation. The first line makes sense, but what was your thought process in introducing G(x) and C(x), and what does the exp function do? Thanks! – 2012-05-27
-
0@Chris Do you understand the symbols I have written? As in: Do you know exp and the sigma notation for sums? – 2012-05-27
-
0@Phira I'm perfectly comfortable with sigma notation, but not this exp thing. – 2012-05-27
-
0@Chris exp is the exponential function. http://en.wikipedia.org/wiki/Exponential_function – 2012-05-27
-
0Oh. Well, now I feel silly. Thank you very much for the answer. – 2012-05-27