How to calculate the number of possible connected simple graphs with $n$ labelled vertices

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}=n2^\binom{n}2\;,$$

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.

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.

We can also reduce the problem of counting the number of labeled simple graphs on $n$ vertices to enumerating partitions of $n$. Our main strategy is to use Mobius inversion on the partition lattice.

Let $G=(V,E)$ be a graph on $n$ vertices. For any subgraph $G'=(V,E')$, where $E'\subseteq E$, we denote $C_{G'}$ to be the partition of vertices corresponding to the connected components of $G'$. We now define $g: \Pi_n \to \mathbb{Z}$ and $f: \Pi_n \to \mathbb{Z}$ as follows. Let $g(B)$ be the number of simple subgraphs $G'=(V,E')$ such that $C_{G'}=B$, and let $f(B)$ be the number of simple subgraphs $G'=(V,E')$ such that $C_{G'}\le B$. Then $$ f(B)= \sum_{A\le B} g(A) $$

We call a partition of $n$ to be type $(k_1,k_2,\dots,k_n)$ if the partition contains $k_i$ blocks of size $i$. Now if $B\in \Pi_n$ has type $(k_1,k_2,\dots,k_n)$, then $$ f(B)= 2^{\sum_{i=2}^n k\dbinom{i}{2}}$$ By Mobius Inversion, we have $$ g(\widehat{1})=\sum_{A\le B}\mu_{\Pi_n}(A,\widehat{1})f(A)$$ Let $\sum_{i=1}^n k_i=k$. Then $|A|=k$, and $[A,\widehat{1}]\cong \Pi_k$. Hence $$\mu_{\Pi_n}(A,\widehat{1})=\mu_{\Pi_k}(\widehat{0},\widehat{1})=(-1)^{k-1}(k-1)!$$ Note that there are $$ \frac{n!}{\prod_{i=1}^n k_i!i!^{k_i}}$$ partitions of $n$ of type $(k_1,k_2,\dots,k_n)$. Thus the number of labeled simple graphs on $n$ vertices is $$ g(\widehat{1})=\sum_{\substack{(k_1,k_2,\dots,k_n) \\ \sum_{i=1}^n ik_i=n}} \left[2^{\sum_{i=2}^n k\dbinom{i}{2}}\right]\left[(-1)^{-1+\sum_{i=1}^n k_i}\right]\left(-1+\sum_{i=1}^n k_i\right)!\left(\frac{n!}{\prod_{i=1}^n k_i!i!^{k_i}}\right) $$

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.

Let $W_n$ be the set of connected graphs with vertex labels from $1, …, n$.

$|W_n| = \sum_{b = 1}^{n-1}(2^{b} - 1) {n-2\choose b-1}|W_{b}||W_{n-b}|$

Proof: First, for any labeled graph, define $C(k)$ to be the component of vertex $k$ in that graph.

Now let $W_{n,S} \subset W_n$ denote the subset of connected graphs on $n$ labeled vertices, such that when vertex $n$ is removed, the $C(1)$ has vertex set $S$.

When varied over choices of $S$, $W_{n,S}$ partitions $W_n$, so $|W_n| = \sum_{S \subset \{1...,n-1\}, 1 \in S }|W_{n,S}|$

Suppose $|S| = b$. Since $S$ must include vertex $1$ and cannot include vertex $n$, there are ${n-2 \choose b-1}$ possible values for $S$. Then there are $|W_b|$ ways to make a connected component out of those vertices in $S$, and $2^b -1 $ ways vertex $n$ can connect to that component (every possible subset of edges except the emtpy subset). And then there are $|W_{n-b}|$ ways the rest of the graph could look like.