Question 10016 – Graph-Theory
February 2, 2024GATE 2002
February 2, 2024Question 9778 – Graph-Theory
How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v1, v2, …,vn} of n vertices?
Correct Answer: D
Question 12 Explanation:
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)
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)
n(n-1)/2
2n
n!
2n(n-1)/2