Wow, slow.

So, I am trying to brute force calculate some properties of the set of subgraphs on n nodes. Up to around n=5 this goes pretty well, takes less than a minute to figure my stuff out. It gets horribly bad very fast though. The thing as least runs now instead of just running out of memory and crashing. However, I built an "estimated time till completion" algorithm so I could make sure that calculations were still being performed and have encountered some unfortunate numbers.

Just my main loop, without even calculating anything about the graphs, has the following ETC(n):

Below n=4 my counter doesn't even start
n=5, ETC~0 seconds
n=6, ETC~7 seconds
n=7, ETC~7 minutes
n=8, ETC~16 hours
n=9, ETC~4000 hours
n=10, ETC~2,000,000 hours (2e6)
n=11, ETC~2,300,000,000 hours (2.3e9)
n=12, ETC~410,000,000,000 hours (4.1e11)
n=13, ETC~20,000,000,000,000,000 hours (2e16)

at which point we have to wait significantly longer than the current age of the universe, ~140,000,000,000,000 hours (1.4e14).

Note for instance that if I actually try and calculate something, the n=10 ETC (for instance) goes from 2e6 hours to 15e6 hours, or 30e6 hours if I try to calculate two things.
My program is much more robust now, it can actually calculate these things I believe, it's just too slow. Even the Monash supercomputer isn't going to help very much. It seems I must accept the limitations of this method.
With a bit of luck I might be able to do up to n=9 on a faster computer than mine, 4000 hours might drop to something reasonable.



Huzzah, a result! I'm sure this is a well known result, it's kind of neat though. Think about it.
If it isn't clear what has happened, I have taken n nodes, found all the subgraphs (undirected, no loops or double edges) and calculated their average degree (number of edges attached to a particular node is it's degree). I then averaged this number over all the subgraphs that can be drawn on n nodes, plotting this on the y-axis. I do this for n=2,3,4,5.