1.2k 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}$
edited | 1.2k views
The answer corresponds to graph without multiple edges and self loops i.e. simple graphs.

@Bikram Am I correct.

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

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

with n vertices we have nC2 edges and each subset of these edges will form a graph, so total number of undirected  graph possible = 2n(n-1)/2

answered by Veteran (13.7k points) 59 156 223
selected by
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)
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 .