# number of different undirected graphs?

The question is:

How many different undirected graphs are there with n nodes and no parallel edges but may include self-loops?

I've been wracking my brain over this for hours now. Basically, I know that for 1 vertex, there are 2 graphs. For 2 vertices, there are 8 graphs. For 3 vertices, there are 64 graphs. However, I can't connect these numbers without my answer for 1 vertices not working. For example, the equation number of graphs equals $2^{3n-3}$ works for 2 and 3 vertices, but not for 1. Any opinions on the connecting equation?

• Don't guess the formula! Think where it comes from. (Though in general it helps to find the formula before understanding why it is true.) Apr 5, 2014 at 1:38
• What does "different" mean? For example, is the two-vertex directed graph with the single edge $12$ the same as the one with the single edge $21$? Apr 5, 2014 at 18:13

Undirected graphs with self-loops on $n$ vertices have $\binom{n}{2} + n = \binom{n+1}{2}$ potential edges. Therefore the are $2^{\binom{n+1}{2}}$ different graphs. For $n = 1,2,3,\ldots$, this is $$2^1, 2^3, 2^6, 2^{10}, 2^{15}, 2^{21}, 2^{28}, 2^{36}, 2^{45}, 2^{55}, \ldots$$