Some Stuff

My newest version of canonical path augmentation code for generating graphs has reached a new high point - generating 11,716,571 graphs on ten vertices. Of course, it also gets the number of nines (261,080) and the number of eights (11,117) correct as well ... which is great, but I'm cautious about declaring it 'correct'. Especially given the last version  did not get the sevens and eights right. See, for example these past failures: So how does it get the right answer? Well, it now properly uses the method mentioned in this post  to only pick canonical deletions that are not cut-vertices . That turns out only to be necessary for graphs on 8 vertices, but you still have to check this for all augmentations, which seems expensive. However, there was a more fundamental problem; consider the example below (basically nicked from Derick Stolee 's blog post): Obviously A and B are isomorphic, yet how do we properly distinguish them? Well, the key is the set of vert