How many undirected graphs (not necessarily connected) can be constructed out of a given set $V = \{v_1, v_2, \ldots, v_n\}$ of $n$ vertices?

How many undirected graphs (not necessarily connected) can be constructed out of a given set $V = \{v_1, v_2, \ldots, v_n\}$ of $n$ vertices? (GATE 2001)

(A) $\frac{n(n-1)}{2}$,

(B) $2^n$,

(C) $n!$,

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

Answer: (D) $2^{\frac{n(n-1)}{2}}$ 

Explanation: 

Here, number of vertices = $n$. 

Therefore, $^nC_2 = \frac{n(n-1)}{2}$ number of edges can be formed. 

Now, each subset of these edges can form an undirected graph (not necessarily connected). 

Therefore, total $2^{\frac{n(n-1)}{2}}$ number of graphs can be formed. 

Next Post