The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+23 votes
2.7k 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?

  1. $\frac{n(n-1)} {2}$
  2. $2^n$
  3. $n!$
  4. $2^\frac{n(n-1)} {2} $
asked in Graph Theory by Veteran (59.5k points)
edited by | 2.7k views
0
The answer corresponds to graph without multiple edges and self loops i.e. simple graphs.

@Bikram Am I correct.
+4

Shivam Chauhan

yes, generally we consider simple graphs, if nothing is mention .

+2

@Bikram Sir
I understood the solution. But, why is

nC0 + nC1 + nC2   . . . . nCn = 2n a wrong answer ?

Since, single vertex graph is also a connected graph and there will be n such graph. Now if we take 2 vertex out of n then we form nC2 graphs and so on . .

What mistake am I committing here ?

+1
Every selection of vertex will also include multiple graphs.

Ex you have chosen 3 nodes in nC3 ways, now u can again form many graphs from it. That's why this answer is wrong
0
^^

Okay, I got it. Thank you.

2 Answers

+34 votes
Best answer
With $n$ vertices we have max possible $^{n}C_{2}$ edges in a simple graph. and each subset of these edges will form a graph, so total number of undirected  graph possible = $2^{\frac{n(n-1)}{2}}$
answered by Boss (13.5k points)
edited by
+18
Another way:

In a complete graph there are [n*(n-1)]/2 edges.

Any of the edge can be selected/neglected, so  2^([n*(n-1)]/2)
+1
Can you please tell the case when I have only few vertices like only v1 ,v2,v3 ,Now this is not counted in these cases as we are just counting the total no of subsets of edges , and the case where we do not chose any edge there we shall have all the vertices isolated from each other , but how to  consider the case where we may have fewer vertices and they still remain isolated .
0
Sorry did nt get ur question ?? can u elaborate it ??
0

I have doubt in this answer , in this question it is not mentioned that graph is labeled. 

hence for n=3 above answer gives number of graphs as 8. But in reality they are 4.

Please refer answer of this question , https://gateoverflow.in/2443/gate1994_1-6-isro2008-29 

Your answer could be correct if graph is labeled 

0
@mehul in question vertices are labeled here. V={v1,v2---vn} that's why we are considering labeled graph.
0 votes

I have doubt in this answer , in this question it is not mentioned that graph is labeled. 

hence for n=3 above answer gives number of graphs as 8. But in reality they are 4.

Please refer answer of this question , https://gateoverflow.in/2443/gate1994_1-6-isro2008-29 

Your answer could be correct if graph is labeled 

answered by Active (1.2k points)


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

37,111 questions
44,694 answers
127,234 comments
43,753 users