The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
303 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 by Active (2.6k points)
edited by | 303 views
0

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

by Veteran (101k points)
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,092 questions
55,323 answers
190,849 comments
86,253 users