Htykuut

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.)

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_kbinom{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}^inftyfrac{2^{n(n-1)/2}}{n!}x^n;,
$$

so

$$
begin{align}
C(x)
&=
1+logsum_{n=0}^inftyfrac{2^{n(n-1)/2}}{n!}x^n
\
&=
1+logleft(1+x+frac2{2!}x^2+frac8{3!}x^3+frac{64}{4!}x^4+dotsoright)
\
&=
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.

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.

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_{Ale 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 $Bin Pi_n$ has type $(k_1,k_2,dots,k_n)$, then
$$ f(B)= 2^{sum_{i=2}^n kdbinom{i}{2}}$$
By Mobius Inversion, we have
$$ g(widehat{1})=sum_{Ale 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 kdbinom{i}{2}}right]left[(-1)^{-1+sum_{i=1}^n k_i}right]left(-1+sum_{i=1}^n k_iright)!left(frac{n!}{prod_{i=1}^n k_i!i!^{k_i}}right) $$

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-2choose 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.

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.