How many simple undirected graphs, not necessarily connected, can be…
2001
How many simple undirected graphs, not necessarily connected, can be constructed on the fixed vertex set V = {v1, v2, ..., vn}?
- A.
n(n - 1) / 2
- B.
2n
- C.
n!
- D.
2n(n - 1) / 2
Attempted by 31 students.
Show answer & explanation
Correct answer: D
Correct answer: 2n(n - 1)/2.
In a simple undirected graph on
nfixed vertices, each edge is an unordered pair of distinct vertices.The number of possible edges is
C(n, 2) = n(n - 1) / 2.Each possible edge can independently be present or absent, so the number of graphs is
2^(number of possible edges).Therefore, total graphs =
2^(n(n - 1)/2).