(Hint: "Purely Functional Datastructures" solves this problem for graphs shaped like a sigle ring. Perhaps this solution can be generalized?)
I can also give more details about rules and conditions, if needed.
P.S. Might as well make it 100 GBP for the first challenge. I am really interested to see whether there's a solution that does it in O(1), like zippers do. (Or alternatively a proof that O(1) to move from node to node is not possible.)
You already know how a zipper for a tree looks like. And you have probably seen a functional queue. Generalizing from both of those, you can imagine how a zipper would work.
I can write down the types and all, even if I don't know of any implementation. But that's probably a topic for a blog post, or so.
The types I was talking about go as: type Context a b = (Adj b, Node, a, Adj b) type Adj b = [(b, Node)]
It definitely allows traversal, and adding nodes seems to be possible, too (judging from the api, of course, it ought to be :)