@Bikram Am I correct.

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?

- $\frac{n(n-1)} {2}$
- $2^n$
- $n!$
- $2^\frac{n(n-1)} {2} $

### 5 Comments

@Bikram Am I correct.

@Bikram Sir

I understood the solution. But, why is

^{n}C_{0 + }^{n}C_{1 + }^{n}C_{2 }_{ . . . . }^{n}Cn = 2^{n }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 ^{n}C_{2 }graphs and so on . .

What mistake am I committing here ?

## 5 Answers

### 9 Comments

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

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**.

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

@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.