Some Stuff

Very occasionally there is a question on math stack exchange that I can actually give some kind of useful answer to. This question  caught my eye; the questioner asks whether graphs with the same degree sequence have the same biconnectivity property. Or to put it another way, are there any pairs of graphs with the same degree sequence but one is biconnected and the other is not? I thought of an example of such a pair, and another user supplied a much simpler one, but here are both pairs: The vertices are coloured by degree (4 = orange, 3 = blue, 2 = green); the red arrows show a transformation of the top graph into its non-biconnected partner. Obviously there may be more than one, I've no idea how many members of a set of isodegree graph might be expected to be biconnected. For the record, here is the transformation of the bottom pair: The red lines bisecting edges indicate a kind of 'bond breaking' although it's not meant to represent an actual chemical r...

So another lesson reluctantly learned... It seems the naïve approach to augmenting molecules by sets of bonds (colored edges, strictly rather than multiple edges) did not work. For example this pair of C9H16 graphs: Thicker lines represent double bonds, and the thinner are singles. The parents of these are non-isomorphic - which is easy to see if you just remove the 6:8 edge from both. However, they cannot be distinguished as augmentations by my current method as the canonical labelling each one gives a graph where the last bond added is the 'natural' canonical choice. The alternative might be to use the canonical labelling method for multigraphs suggested by the  nasty  manual which involved transforming the multiedge graph into a layered simple graph. This is illustrated in this example: The transformation converts single edges into an edge in the first layer, and multiple edges into an edge in the second layer (and so on). Highlighted in purple is an example ...