Ah yes, I think I understand - I'd looked at the perfect match algorithm before, but discarded it then because at the time I was trying to solve the splitting problem for which I needed specifically a cycle, and it looked like extending the algorithm to require a cycle was going to degenerate it into something no better than the brute force.

If I'm no longer looking for a cycle, then I can probably use that algorithm. I'll give it a go, and come back.

Update: I *do* understand now. I had read your approach as "to check the edge uv, remove the edge and check ...", but eventually worked out that couldn't be right, that I had to remove the two vertices instead.

What's more, thinking about it in the graph form it is clear to me that after cleanup the split also becomes trivial - the graph simply falls apart into disconnected subgraphs.

Thanks,

Hugo

Excellent, it works. :)

The code below demonstrates and tests the cleanup() method and its dependencies - the rest is just a minimal hack to wrap a test harness around it. I also hacked in %rev at the last minute when I realised %$assign was the wrong way round for my needs, I still need to refactor that.

Thanks very much for your help,

Hugo