Graphs Problem 4

Solution

Any edge in a graph links two distinct vertices. The graph is undirected, therefore the way to pick such two vertices out of a total of n vertices is \(n(n-1)/2\). Furthermore, for any possible edge, there are two possibilities: either it is in the graph or it is not. So the number of possible graphs is \(2^{n(n-1)/2}\).