edited by
1,355 views
4 votes
4 votes

How many undirected graphs are possible with n vertices

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

1 Answer

Best answer
3 votes
3 votes

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

Related questions

76 votes
76 votes
12 answers
1
Kathleen asked Oct 4, 2014
34,432 views
The number of distinct simple graphs with up to three nodes is$15$$10$$7$$9$
2 votes
2 votes
2 answers
2
0 votes
0 votes
1 answer
3
Sahil Gupta asked Dec 16, 2014
481 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...
4 votes
4 votes
2 answers
4
Balaji Jegan asked Nov 27, 2018
2,486 views
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ?There is a condition that adjacent...