https://gateoverflow.in/2443/gate1994_1-6-isro2008-29

Both these question gave rise to my confusion.

The Gateway to Computer Science Excellence

+3 votes

How many undirected graphs are possible with n vertices

- if graphs are not necessarily connected
- if they are necessarily connected

0

https://gateoverflow.in/733/gate2001-2-15

https://gateoverflow.in/2443/gate1994_1-6-isro2008-29

Both these question gave rise to my confusion.

https://gateoverflow.in/2443/gate1994_1-6-isro2008-29

Both these question gave rise to my confusion.

+3 votes

Best answer

In the question that came in GATE 1994 , it is just asking number of simple graphs having upto 3 vertices and hence we should not bother about connectivity..

And in the question which came in GATE 2001 , it asked about the number of simple graphs of n vertices which is not necessarily connected which means it may be connected or may not be.So we have to include both types of graphs and hence connectivity is not a concern here as well..

So for both of them , the answer would be : 2^{(n(n-1)/2)} as we can have maximum of n(n-1) / 2 edges and each edge can be selected or rejected for formation of the graph..

However if we are asked : Number of simple undirected graphs which are necessarily connected and has 'n' vertices , then this problem's complexity becomes higher as we need to take connectivity for each graph into consideration as well..

For labelled graphs of n vertices , the following recurrence is used :

* Σ ^{n}C_{k }* k * d_{k }* 2^{(n-k)(n-k-1)/2} = n * 2^{n(n-1)/2} * where d

For more ref , u may check the link : https://math.stackexchange.com/questions/154941/how-to-calculate-the-number-of-possible-connected-simple-graphs-with-n-labelle

+1

So for both of them , the answer would be : 2

^{(n(n-1)/2)}

^{Then for the GATE 1994 question, with 3 vertices, number of graph possible should be }2^{(3(3-1)/2) = 8, but on one of the answer it is written that }

*total number of unlabled simple graphs on 3 nodes will be 4.*

I am sorry, but I am missing something here, I am not getting it.

0

Since it is unlabelled simple graphs , hence we would get same unlabelled graph for a few labelled graph and hence in this case we have to manually check which is not difficult to do for n = 3.

+1

^{Then for the GATE 1994 question, with 3 vertices, number of graph possible should be }2^{(3(3-1)/2) = 8, but on one of the answer it is written that }

total number of unlabled simple graphs on 3 nodes will be 4.

I am sorry, but I am missing something here, I am not getting it.

That formula is for Labelled simple Graph .

Here they are asking for unlabelled for upto 3 node. So just draw graph for 1 node , 2 node and 3 node you will get graph as follows :

Total = 7

52,218 questions

59,876 answers

201,073 comments

118,119 users