This “interesting challenge” from @littmath set me off on a very interesting journey. I thought maybe I should share some of what I found on that journey, because I really enjoyed it. https://twitter.com/littmath/status/1285010124445229056

It’s one of those lovely places where different areas of mathematics, that are accustomed to shun one another, come together in a happy and beautiful dance.

The word “unlabeled” is what makes this question non-trivial. If the graph nodes are labelled, these two graphs are different:

But if the labels are removed, they’re indistinguishable. Formally, there is a permutation of the labels that maps one to the other.

Counting *labelled* graphs is not very interesting. If we have n labelled nodes, there are (n choose 2) possible edges; so there are 2^(n choose 2) possible labelled graphs on n nodes.

Similarly there are ((n choose 2) choose k) different k-edge graphs on n labelled nodes.

Counting unlabelled graphs is much harder. There isn’t a simple formula – or indeed any formula at all, as far as I know. So there isn’t even really an obvious place to start with @littmath’s question.

Okay, sorry for the long preamble.

The proof uses what Richard Stanley – the great combinatorialist who popularised this technique – calls the Linear Algebra Paradigm.

The idea is to define a vector space where the basis vectors are *all the labelled graphs with n nodes*. So a vector in this space is like a weighted set of labelled graphs.

But wait! What is this? We’re interested in *unlabelled* graphs!

Unlabelled graphs are represented by a *subspace* of this vector space. Given an unlabelled graph, represent it as the formal sum of all the possible labellings of that graph!

(Sorry, real life has intervened just as this thread was getting interesting. I’ll delete this holding tweet and resume it, when I can.)