self doubt

Question

What is the general formula for  number of  simple graph having n unlabelled vertices ??

Comments

In graph why we care about labelled or not?

All vertices  are treated as distinct nodes..

Am i right?

---

@Verma Ashish Take $3$ vertices...and if you don't give them a name like $A$,$B$ and $C$ and when you try to make simple graphs with these vertices then some graphs will be isomorphic and when you give them a name then all possible graphs will be considered as distinct graphs...

There is no closed form formula to find no. of unlabeled simple graphs with $n$ vertices but we can find no. of simple graphs with $n$ labeled vertices as you have given above. Since, maximum edges are $^{n}C_{_{2}}$. So, 2 choices for choosing each edge. So, it becomes $2^{^{n}C_{_{2}}}$

There is no closed form formula to find no. of unlabeled simple graph with $n$ vertices but it will always be less than $2^{^{n}C_{_{2}}}$  because some graphs will be same due to its isomorphic nature.

---

Yes..

You are right👍

That will be for labeled undirected simple graph..

Answer 1

For "n" vertices we have  ways "n ! " to label them and for each way we have among n! Labelling we have 2^ (n(n-1) / 2 ) graphs so the answer is

N! (2 ^ (N (N-1)/ 2 )  total unlabelled graph where N is total no. of vertices

Comments

@rballiwal

How are u deriving this formula for the unlabelled graph?

---

This formula is wrong.

Answer 2

2n!/(n+1)!n!