1. ## Number of Graphs

I came across a formula for number of graphs on n vertices as $\displaystyle 2^(^n^c^2^)$

Can anyone explain me how this formula is arrived.

I trying to find by having adjacency matrix representation of a graph in mind. But i am not able to achieve this.

2. Originally Posted by kumaran5555
I came across a formula for number of graphs on n vertices as $\displaystyle 2^(^n^c^2^)$

Do you mean $\displaystyle 2^{\binom{n}{2}}=2^{\frac{n(n-1)}{2}}~?$

3. There are nC2 pairs of vertices. Each of them can be or not be an edge.

An adjacency matrix for a simple undirected graph (at most one edge between two vertices and no loops) is symmetric and has 0's on the diagonal. The number of elements in the half above the diagonal is n(n - 1)/2 = nC2. Each of them can be 0 or 1.

4. If my guess is correct, that number on the OP is for simple graphs on n labels. The more general question about unlabeled simple graph is much more difficult.
There are only four unlabeled simple graph of order three.
However that are, $\displaystyle 2^{\binom{3}{2}}=8$ labeled simple graphs of order three.

We choose the labels two at a time to form the edges.
Any subset of edges is a graph.

Polya solved the unlabeled simple graph problem in 1935. But very complicated.

5. Thanks.

I think it almost similar to the way we prove for number of reflexive relations of a set with n elements.