1
$\begingroup$

The question is:

How many different undirected graphs are there with n nodes and no parallel edges but may include self-loops?

I've been wracking my brain over this for hours now. Basically, I know that for 1 vertex, there are 2 graphs. For 2 vertices, there are 8 graphs. For 3 vertices, there are 64 graphs. However, I can't connect these numbers without my answer for 1 vertices not working. For example, the equation number of graphs equals $2^{3n-3}$ works for 2 and 3 vertices, but not for 1. Any opinions on the connecting equation?

$\endgroup$
2
  • $\begingroup$ Don't guess the formula! Think where it comes from. (Though in general it helps to find the formula before understanding why it is true.) $\endgroup$ Apr 5, 2014 at 1:38
  • $\begingroup$ What does "different" mean? For example, is the two-vertex directed graph with the single edge $12$ the same as the one with the single edge $21$? $\endgroup$ Apr 5, 2014 at 18:13

1 Answer 1

4
$\begingroup$

Undirected graphs with self-loops on $n$ vertices have $\binom{n}{2} + n = \binom{n+1}{2}$ potential edges. Therefore the are $2^{\binom{n+1}{2}}$ different graphs. For $n = 1,2,3,\ldots$, this is $$ 2^1, 2^3, 2^6, 2^{10}, 2^{15}, 2^{21}, 2^{28}, 2^{36}, 2^{45}, 2^{55}, \ldots $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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