# GATE2001-2.15

6.7k 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
0
The answer corresponds to graph without multiple edges and self loops i.e. simple graphs.

@Bikram Am I correct.
9

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

3

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

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

Okay, I got it. Thank you.

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
38
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)
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 .
0
Sorry did nt get ur question ?? can u elaborate it ??
0

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.

4
@mehul in question vertices are labeled here. V={v1,v2---vn} that's why we are considering labeled graph.
0
Great explanation..thnx
1
What if they had asked “how many CONNECTED graphs can be constructed” ?
0

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.

0
Here we assume vertices are labelled .

if vertices are not labeled then less graphs possible.

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
0
sir, i think you forgot to divide the exponent by 2.
0
Thanks for pointing it out, Mate!

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.

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

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.

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

Correct ans- D
With n vertices no. of possible edges = n C 2
Each subset of these edges will be form a graph.
No. of possible undirected graphs is 2(n C 2)
⇒ 2(n(n-1)/2)

## Related questions

1
2.3k views
Consider a weighted undirected graph with vertex set $V = \{n1, n2, n3, n4, n5, n6 \}$ and edge set $E = \{(n1,n2,2), (n1,n3,8), (n1,n6,3), (n2,n4,4), (n2,n5,12), (n3,n4,7), (n4,n5,9), (n4,n6,4)\}$. The ... tree unique over all possible minimum spanning trees of a graph? Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning tree of a graph?
Consider a relation geq which represents "greater than or equal to", that is, $(x,y) \in$ geq only if $y \geq x$. create table geq ( ib integer not null, ub integer not null, primary key ib, foreign key (ub) references geq on delete cascade ); Which of the following is possible ... deleted A tuple (z,w) with z > x is deleted A tuple (z,w) with w < x is deleted The deletion of (x,y) is prohibited
Which of the rational 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]\right)\right\}$ ... $\left\{t \mid \exists u \in R_1\left(t[A]=u[A]\right) \land \exists s \in R_2 \left(t[A] = s[A]\right)\right\}$
$R(A,B,C,D)$ is a relation. Which of the following does not have a lossless join, dependency preserving $BCNF$ decomposition? $A \rightarrow B, B \rightarrow CD$ $A \rightarrow B, B \rightarrow C, C \rightarrow D$ $AB \rightarrow C, C \rightarrow AD$ $A \rightarrow BCD$