edited by
13,972 views
52 votes
52 votes

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} $
edited by

6 Answers

Best answer
68 votes
68 votes
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}}$

Correct Answer: $D$
edited by
7 votes
7 votes

No. of vertices in the given questions $= n$

In an undirected simple graph, the maximum no. of edges that are possible $= n(n-1)/2$

Now, each edge can be either present or absent in a graph. So, there are 2 possibilities for each vertices.

Therefore, total no. of possible graphs $= 2*2*2*...  n(n-1)/2$ times

=$2^{n(n-1)/2}$ 

So, correct answer is option no. D.

edited by
1 votes
1 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 

Answer:

Related questions

29 votes
29 votes
3 answers
1
46 votes
46 votes
6 answers
3
Kathleen asked Sep 14, 2014
8,531 views
Which of the following relational calculus expression is not safe?$\left\{t \mid \exists u \in R_1\left(t[A] = u[A]\right) \land \neg \exists s \in R_2 \left(t[A] = s[A]\...
128 votes
128 votes
6 answers
4