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

^^

Okay, I got it. Thank you.

---

you can even do it by deriving and solving the recurrence relation: T(n) = 2⁽ⁿ⁻¹⁾ * T(n-1)

---

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

Answer 1

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)

Answer 2

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]