How many undirected graphs (not necessarily connected) can be constructed out…
2025
How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {V₁, V₂, ..., Vₙ} of n vertices?
- A.
n(n − 1)/2
- B.
2ⁿ
- C.
n!
- D.
2^(n(n − 1)/2)
Attempted by 97 students.
Show answer & explanation
Correct answer: D
The number of undirected graphs on n vertices is determined by considering all possible edges. There are n(n-1)/2 distinct pairs of vertices, and each pair can either have an edge or not. This gives 2^(n(n-1)/2) possible graphs.
This formula accounts for all combinations of edges, including disconnected graphs.