# Number of distinct graphs in $n$ vertices

So we know that the number of distinct simple undirected graphs (i.e. no loops or double edges) in $$n$$ vertices is $$2^{\binom{n}{2}}$$, but what if we allow loops or double edges? My thought: For each pair of vertices $$v_i, v_j$$, there are now 3 distinct possibilities (no edge $$v_iv_j$$, single edge $$v_iv_j$$ or double edge $$v_iv_j$$). Also for each vertex there are two possibilities (there is or there isn't a loop), so in total I count $$2 \times 3^{\binom{n}{2}}$$ distinct undirected graphs, is that correct?

• what about multiple loops? May 16 at 22:31

I think you mean $$2^n 3^{\binom n 2}$$. That should be correct assuming there's either one or no loop at each vertex.

Usually, once you allow multiple edges you can have any number of edges between two vertices, so there are infinitely many possible graphs.