Question

You may assume there are exactly $2^\binom{n}{2}$ simple graphs with vertex set

Answer 1

.Each graph G with vertex set V is uniquely determined by its edge set E. E must be a subset of $\binom{V}{2}$ , the set of all pairs in V . We have seen already that every set with m elements has 2^m different subsets. In our case,

m = $\left | \binom{V}{2} \right |$    =
2
, hence there are 2
²
different graphs with vertex set V .