0
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ what about multiple loops? $\endgroup$
    – kodlu
    May 16, 2021 at 22:31

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .