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 Junior (911 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.2k points) 15 58 293
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

    23338 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7912 Points

  4. srestha

    6238 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4968 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4286 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3794 Points


Recent Badges

Popular Question user1234
Copy Editor Ayush Upadhyaya
Popular Question asu
Popular Question .
Popular Question makhdoom ghaya
Popular Question junaid ahmad
Notable Question learner_geek
Notable Question jothee
Popular Question jothee
Notable Question Jeffrey Jose
27,290 questions
35,142 answers
83,926 comments
33,231 users