Well, you can use weak pointers appropriately in a safe setting. It's not fun though. Alternately, you can use a layer of indirection, such as throwing all your graph nodes in a big vector and having them use indices to refer to one another.

So I would perhaps revise that statement to "easy cyclic data structures, memory safety, memory management without tracing, pick two".

Fair enough. But with the vector approach, now you can have something that looks a lot like a use-after-free error!

Yes, you can, but it doesn't result in type confusion, which reduces its severity.