Non-isomorphic graphs with four total vertices, arranged by size

Question

I am using the book Graph Theory: A Problem Oriented Approach. One of the problems asks to list all the non-isomorphic graphs that can be made with four vertices. Fair enough, there are eleven total such non-isomorphic graphs. Then I grouped each graph with its corresponding complement, and there is one graph with three edges that is isomorphic to it's own complement.

There are six edges possible for a graph with four vertices. The number of non-isomorphic graphs corresponding to the number of edges is as follows: $$ 0\!:\!1\quad 1\!:\!1\quad 2\!:\!2\quad 3\!:\!3\quad 4\!:\!2\quad 5\!:\!1\quad 6\!:\!1 $$ I am having a hard time correlating the number of non-isomorphic graphs corresponding to the given number of edges. I first saw that it looks like the a reflected Fibonacci sequence, so out of desperation I tried finding an expression using binomial coefficients that can explain the number of graphs for each edge. Any hints that will put in the right direction will be appreciated, or any explanations that use or don't use binomial coefficients.

Answer 1

Counting the number of distinct simple graphs on a given number of edges and vertices is a difficult problem. See OEIS sequence A008406. Below I've arranged the sequence into rows based on the number of vertices $(n)$ and arranged each row by the number of edges from $0$ to $\frac{1}{2}n(n-1)$. \begin{align} &1\tag{1}\\ 1&\;1\tag{2}\\ 1\;1&\;1\;1\tag{3}\\ 1\;1\;2\;&3\;2\;1\;1\tag{4}\\ 1\;1\;2\;4\;6\;&6\;6\;4\;2\;1\;1\tag{5}\\ 1\;1\;2\;5\;9\;15\;21\;24&\;24\;21\;15\;9\;5\;2\;1\;1\tag{6}\\ 1\;1\;2\;5\;10\;21\;41\;65\;97\;131\;148&\;148\;131\;97\;65\;41\;21\;10\;5\;2\;1\;1\tag{7}\\ &\vdots \end{align} Each row does look kinda Fibonacci-ish, but the resemblance is superficial. The OEIS page mentions two rather complicated ways of computing these number^[1][2]. All the simple ways of computing them listed on the page are to do little more than just build all graphs on a given number of edges and vertices, delete duplicates up to isomorphism, and count them.

---

1. Leonid Bedratyuk, A new formula for the generating function of the numbers of simple graphs,
   arXiv:1512.06355 [math.CO], 2015.

2. F. Harary and E. M. Palmer, Graphical Enumeration, page 83