search
Log In
3 votes
450 views

How many undirected graphs are possible with n vertices

  1. if graphs are not necessarily connected
  2. if they are necessarily connected
in Graph Theory
edited by
450 views

1 Answer

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 :

Σ 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 by
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

44 votes
9 answers
1
12.5k views
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
asked Oct 4, 2014 in Graph Theory Kathleen 12.5k views
36 votes
3 answers
2
5.5k views
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} $
asked Sep 15, 2014 in Graph Theory Kathleen 5.5k views
2 votes
2 answers
3
726 views
Consider the graph G whose vertices are 4 element subsets of the set {1, 2, 3…10} with two vertices adjacent if and only if their intersection is empty. Then the number of edges does G have _______
asked Nov 28, 2016 in Graph Theory Akriti sood 726 views
0 votes
1 answer
4
207 views
Consider the following set : {1,2,3,.....n}. Now consider all possible subset. Two subset S1 and S2 are having edge between them only if their intersection has two common elements. Find: a) Number of isolated vertices. b) Number of components c) Highest degree possible ... single element set, phi and itself. So its degree is 2n - n - 2 which must be highest. Please suggest suitable approach to it.
asked Dec 16, 2014 in Graph Theory Sahil Gupta 207 views
...