in Graph Theory edited by
10,775 views
42 votes
42 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} $
in Graph Theory edited by
10.8k views

4 Comments

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
4
4
^^

Okay, I got it. Thank you.
0
0
you can even do it by deriving and solving the recurrence relation: T(n) = 2⁽ⁿ⁻¹⁾ * T(n-1)
0
0

5 Answers

63 votes
63 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}}$

Correct Answer: $D$
edited by

4 Comments

What if they had asked “how many CONNECTED graphs can be constructed” ?
1
1
edited by

If they asked like "Necessarily connected" then i think we can have 

a minimum of  C ( n*(n-1)/2 , (n-1)) graphs

and a maximum of  C( n*(n-1)/2  ,  ((n-1)(n-2)/2)+1) graphs.

Anyone please clarify.

0
0
Here we assume vertices are labelled .

if vertices are not labeled then less graphs possible.
0
0
5 votes
5 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

2 Comments

sir, i think you forgot to divide the exponent by 2.
0
0
Thanks for pointing it out, Mate!
0
0
1 vote
1 vote

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 

3 Comments

can u help me how u find the value of n(n-1)/2.??plese explain i cant understand
0
0
then what is v1,v2,v3,....vn.??

are not they labels...read carefully
0
0

@mehul vaidya In gate 1994 question asked upto 3 nodes i.e you consider 0 node , 1 node , 2 nodes and 3 nodes.

But Question based on unlabeled graphs because they asked upto 3 nodes

     so for and 3 nodes we construct 4 different unlabeled graphs

As 3 vertex with 3 edges = 1 graph

  3 vertex with 2 edges = 1 graph

3 vertex with 1 edge = 1 graph

3 vertex with 0 edge = 1 graph

similarly 2 nodes we construct 2 different unlabeled graphs

2 vertex with 2 edges = 0 graph

2 vertex with 1 edges = 1 graph

2 vertex with 0 edges = 1 graph

and  1 nodes we construct only 1 unlabeled graphs

 1 vertex with 1 edges = 0 graph

1 vertex with 0 edges = 1 graph

these are the total 7 unlabeled graphs construct

and out of these 7 graphs only 4 graphs are connected....

which are  

3 vertex with 3 edges = 1 graph

  3 vertex with 2 edges = 1 graph

2 vertex with 1 edges = 1 graph

1 vertex with 0 edges = 1 graph  ( single node also called as connected graph in 1 vertex graph ).

if you considering Labeled graph then formula is 2^n(n−1)/2

for 3 node = 2^3(3-1)/2 = 8 labeled graphs construct

for 2 nodes = 2 labeled graphs construct

for 1 node = 1  labeled graphs construct

so total 11 graphs generates , if Labeled graph taken.

I hope now you cleared doubts.

0
0
0 votes
0 votes
3C0 + 3C1 + 3C2 + 3C3 = 8

Correct ans- D
Answer:

Related questions