2
$\begingroup$

How many non-isomorphic simple graphs are there on n vertices when n is 2? 3? 4? and 5?

So I got...

$2$ when $n=2$

$4$ when $n=3$

$13$? (so far) when $n = 4$ But I have a feeling it will be closer to 16.

I was wondering if there is any sort of formula that would make finding the answer easier than just drawing them all out. And if not, if anyone could confirm my findings so far.

$\endgroup$
4
$\begingroup$

There is no nice formula, I’m afraid. What you want is the number of simple graphs on $n$ unlabelled vertices. For questions like this the On-Line Encyclopedia of Integer Sequences can be very helpful. I searched in on the words unlabeled graphs, and the very first entry returned was OEIS A000088, whose header is Number of graphs on n unlabeled nodes. A quick check of the smaller numbers verifies that graphs here means simple graphs, so this is exactly what you want. It tells you that your $1,2$, and $4$ are correct, and that there are $11$ simple graphs on $4$ vertices. You should check your list to see where you’ve drawn the same graph in two different ways. If you get stuck, this picture shows all of the non-isomorphic simple graphs on $1,2,3$, or $4$ nodes. The OEIS entry also tells you how many you should get for $5$ vertices, though I can’t at the moment point you at a picture for a final check of whatever you come up with.

$\endgroup$

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.