GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
42 views

How many undirected graphs are possible with n vertices

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

 

asked ago in Graph Theory by Active (1.1k points) 1 10
edited ago by | 42 views

1 Answer

+1 vote
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

answered ago by Veteran (88.5k points) 15 58 294
selected ago by

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.


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
Top Users Oct 2017
  1. Arjun

    23396 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8158 Points

  4. srestha

    6286 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4344 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Popular Question LavTheRawkstar
Great Question jothee
Notable Question Priyanka23
Great Question khushtak
Good Question Ishrat Jahan
Good Answer Arjun
Revival Arjun
Nice Question Kathleen
Nice Answer janakyMurthy
Renewal janakyMurthy
27,316 questions
35,169 answers
84,075 comments
33,262 users