I came across a formula for number of graphs on n vertices as
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.
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.
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, 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.