GATE2001-2.15 GATE1994-1.6

Question

How many undirected graphs are possible with n vertices

1. if graphs are not necessarily connected
2. if they are necessarily connected

Comments

https://gateoverflow.in/733/gate2001-2-15
https://gateoverflow.in/2443/gate1994_1-6-isro2008-29

Both these question gave rise to my confusion.

---

Video Explanation of Part 1: https://youtu.be/EbX7TV0ao6o  

Answer 1

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 :

Σ ⁿC_k  * k * d_k * 2^{(n-k)(n-k-1)/2}    =     n * 2^n(n-1)/2    where d_n is the number of labelled, connected, simple graphs on n vertices.

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

Comments

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.

---

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.

---

^{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

---

Yeah. I cleared ths doubt earlier. Thank you. :)