Why does the Number of Graphs on $n$ Vertices Blow up so Quickly?

Question

See for example here: https://en.wikipedia.org/wiki/Graph_enumeration

I would have thought (naively) that the number of graphs on $n$ vertices would only grow as $\mathscr{O}\left( _nC_2\right)$, but it clearly grows much faster. Even the number of trees blows up faster than the factorial.

https://en.wikipedia.org/wiki/Cayley%27s_formula

Why does the number of graphs blow up so much faster than almost anything else?

I would have thought it would have just been a question of selecting which 2 vertices of $n$ to connect with an edge, which seemingly can be done with $\mathscr{O}\left( _nC_2\right)$ time. What am I missing?

Answer 1

$\binom{n}{2}$ is the number of potential edges in a graph with $n$ vertices. Every subset of the set of edges makes a graph, so there are $$ 2^{\binom{n}{2}} $$ graphs. That grows pretty quickly.

Answer 2

In addition to the first answer, I think it's worth mentioning that the more meaningful quantity here is not the number of all graphs on $n$ labeled vertices, which is $2^{{n\choose 2}}$ as already pointed out, but the number of non-isomorphic graphs on $n$ vertices, since for example there are $n!/2$ ways that the same graph $\cdot\to \cdot \to \ldots\to \cdot$ can be realized if you care about the labels. The number of nonisomorphic graphs on $n$ vertices is trivially lower bounded by $$ \frac{2^{{n\choose 2}}}{n!}\approx 2^{n^2/2-n\log n}$$ (see this question), so it's still a huge number