# Connected Cubic Graph Counting

I want to count the number of connected and disconnected cubic non-isomorphic graphs with vertices $$2n$$, but I haven't been able to come up with an algorithm or technique to do so. I've been researching for the past 2 days and haven't found anything convincing.

Techniques I've tried is converting the graphs to adjacency matrices and looking for pattern, using combinatorics, two-colour theory and so on.

I know the sequence of connected cubic graphs for $$2,4,6,8,10,12,14,...,2n$$ vertices as $$0,1,2,5,19,85,509,\ldots$$, but how do you derive proceeding graph counts from preceding ones? How do you go from $$5$$ to $$19$$ to $$85$$ and so on?

I have no idea. I need some clarity on this problem and possible solutions.

• The connected ones are tabulated at oeis.org/A002851 and there are references there which should give you some idea of how those counts were found. No formula, recursive or otherwise, is given there, so I expect that none is known. Commented Oct 13, 2021 at 12:25
• There is an article by Brinkmann,Goedgebeur, McKay "Generation of Cubic graphs". The article is very interesting. Maybe it will help you. Commented Oct 13, 2021 at 12:42

I figured it out last night and the answer is fairly straight forward, and not really.

Counting connected graphs is an NP hard problem and although there are algorithms, they relatively computationally complex, not something you can solve on paper with a pen.

As Gerry pointed out, A002851 shows a series for connected graphs, but what if we wanted to derive disconnected graphs from those connected graphs, or get total graphs?

Here is the solution.

There is 1 cubic graph order 4. This is trivial as we know each vertex needs 3 edges, therefore there is only one non-isomorphic graph of V=4.

For cubic graph order 6, there are 2 non-isomorphic graphs. This can be derived from its edges. As there are 6-4=2 edges that can be moved to create another isomorphism, there can only be 2 non-isomorphic graphs. Additionally, this graph cannot be disconnected, so there are no disconnected cubic sub-graphs.

For order 8, there are 5 connected non-isomorphic graphs and 1 disconnected non-isomorphic graph. We know this as order 8 can be split into two order 4 cubic graphs.

For order 10, we use our results from order 6 and 4. As order 6 as two non-isomorphic graphs and we know there are 19 connected non-isomorphic graphs, we can determine that order 4 plus order 6A and order 6B make up the rest of the disconnected non-isomorphic graphs.

For order 12, there are sub-cubic graphs of order 6 and 6, order 8 and 4, and order 4*3. We know there are 85 connected cubic graphs of order 12, and now with the those sub-cubic graphs we can determine that 6A/6B, 6A/6A, 6B/6B, 8A-E/4 and 4/4/4 make up the disconnected graphs of order 12, increasing the total to 85+9= 94 cubic graphs order 12.

For order 14, we do the same for 4/10, 6/8, 6/4/4, which turns out to be 31 disconnected graphs plus 509 connected graphs, for a total of 540 cubic graphs and so on.

Thus, we have derived total cubic graphs using disconnected cubic graphs and connected cubic graphs until we run out of connected graphs, which I have yet to solve (someday).