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?

  • 2
    $\begingroup$ what about multiple loops? $\endgroup$
    – kodlu
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.