GATE CSE 2001 | Question: 2.15

Question

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?

• A. $\frac{n(n-1)} {2}$
• B. $2^n$
• C. $n!$
• D. $2^\frac{n(n-1)} {2} $

Comments

Video Explanation: https://youtu.be/EbX7TV0ao6o 

---

Option elimination can be done in exam,

Take n = 3, you will get 8 different graphs --> so option C and A ruled out.
now take n = 2 you will get 2 different graps --> So option B ruled out.

---

we have n vertices
So for every pair of vertex we have two choice 1. we put a edge
                                                                           2. we don't put a edge
total possible case 2^nC2

Ex. let n=3,than possible number of groups is 8
which lablled or unlabelled, We have three edge and every edge has three choice
than total case 2*2*2 = 2^3

Option D is Correct

Answer 1

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$

Comments

got it

---

@꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂ is your answer correct for necessarily connected?

---

@dsevta , go through this once 

Answer 2

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.

Comments

sir, i think you forgot to divide the exponent by 2.

---

Thanks for pointing it out, Mate!

Answer 3

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 

Comments

can u help me how u find the value of n(n-1)/2.??plese explain i cant understand

---

then what is v1,v2,v3,....vn.??

are not they labels...read carefully

---

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

Answer 4

We can take a small value of n like n=2 and n=3 and validate in  exam using the options  but lets see full analysis of this question

 

Let there be n vertices as stated in the question.An undirected simple graph will not contain self loops and multiple edges.So between any two vertices only an edge is possible

 

If we have 3 vertices v1,v2 and v3  we can put edges between {v1,v2},{v1,v3} and {v2,v3}.Since these are undirected so (v1,v2) ==(v2,v1).So only three edges(atmost) are possible.Similarly for n vertices utmost n edges are possible.wrong!Consider n=4 we can have 6 edges rather than 4 [{v1,v2},{v1,v3},{v1,v4},{v2,v3},{v2,v4},{v3,v4}].If we closely inspect we are rather choosing any pair of vertices and placing an edge between them.So the no of ways to pair from n elements is $^{n}$C$_{2}^{}\textrm{}$.

Every edge has two possibilities either the edge will be present or the edge will be absent.So the total no of simple undirected graphs are 2*2*2*...*2(nC2-times)=2^($^{n}$C$_{2}^{}\textrm{}$)=2^(n(n-1)/2)[Option d]

Answer 5

We could think from a vertex point of view, since each vertex is labelled then first vertex $v_1$ has $n-1$ other vertices to chose to form an edge with or not i.e it has 2 options for each of $n-1$ vertices, overall $v_1$ will produce have $2^{(n-1)}$ possible combinations.

Now since the graph is undirected an edge from $v_1$ to $v_2$ is same as an edge from $v_2$ to $v_1$ so the next vertex $v_2$ will have $2^{n-2}$ options and so for $v_3, v_4, ....v_n....$ we will have $2^{n-3.},2^{n-4}...2^{n-n}$ combinations .

In total we will have :

                                                  Total Graphs = $2^{n-1}*2^{n-2}*......2^{0}$

                                                                      = $2^{(n^2)-(1+2+3+.....n)}$

                                                                      = $2^{(n^2)-\frac{n*(n+1)}{2}}$

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

 Which is the answer $(D)$

 

 

 

 

Answer 6

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

Correct ans- D