# GATE2001-2.15 GATE1994-1.6

450 views

How many undirected graphs are possible with n vertices

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

edited

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 :

Σ nCk  * k * d* 2(n-k)(n-k-1)/2    =     n * 2n(n-1)/2    where dn 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

selected
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

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

## Related questions

1
12.5k views
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n-1)} {2}$ $2^n$ $n!$ $2^\frac{n(n-1)} {2}$