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$
  • $\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$ – Yuval Filmus Apr 5 '14 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$ – David Richerby Apr 5 '14 at 18:13
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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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