How many undirected graphs (not necessarily connected)

Home » Programming & Data Structure » Programming and data structure miscellaneous » Question

How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v₁ , v₂ ,....,v_n }of n vertices ?

1. n(n - 1)
  2
2. 2ⁿ
3. n!
4. 2^{n(n - 1) / 2}

Correct Option: D

Here, we need to find the number of undirected graphs to be constructed
Now, S = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8... n – 1
= n (n – 1)/2 → constructed graphs = 2^S
= 2^{n(n - 1) / 2}

	n(n - 1)
	2