0 votes 0 votes What is the general formula for number of simple graph having n unlabelled vertices ?? Graph Theory simple-graph + – Doraemon asked Mar 31, 2019 Doraemon 1.3k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Verma Ashish commented Mar 31, 2019 reply Follow Share In graph why we care about labelled or not? All vertices are treated as distinct nodes.. Am i right? 0 votes 0 votes ankitgupta.1729 commented Mar 31, 2019 reply Follow Share @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. 6 votes 6 votes Verma Ashish commented Mar 31, 2019 reply Follow Share Yes.. You are right👍 That will be for labeled undirected simple graph.. 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes 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 rballiwal answered Jun 4, 2019 rballiwal comment Share Follow See all 2 Comments See all 2 2 Comments reply Doraemon commented Jun 4, 2019 reply Follow Share @rballiwal How are u deriving this formula for the unlabelled graph? 1 votes 1 votes Crackca commented Dec 13, 2021 reply Follow Share This formula is wrong. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 2n!/(n+1)!n! Muneendra1337 answered Nov 29, 2019 Muneendra1337 comment Share Follow See all 0 reply Please log in or register to add a comment.