Graph theory Narshing Deo

Question

theorem no 10.1 Narsingh Deo

prove that the no. of labeled graph of n vertices of n is 2^(n(n-1)/2)

Answer 1

When we have $n$ vertices and each is labelled, or to say that each vertex is distinct. Then we can have a maximum of $\frac{n(n-1)}{2}$ edges, one between every pair, (maximum edges are in a complete graph). Now for each edge, we have 2 choices, either it will be in the graph, or it won't be.

This gives a total of $2^{\frac{n(n-1)}{2}}$ possible different graphs.

NOTE:

We here have counted simple undirected graphs only, i.e. which do not have self-loops and multiple edges between the same pair of vertices.