> it also introduces other subtle bugs if your logic is wrong (e.g. you have edge 100 but actually those nodes were removed, so now you're pointing at the wrong node

This is not actually a different kind of bug; it's just use-after-free, which you can of course get when using pointers instead of indices.

Actually it's slightly safer than pointer use-after-free because it is type safe and there's no UB.

Also some of the Rust arenas give you keys (equivalent to pointers) which can check for this. There's a good list here (see "ABA mitigation"):

https://donsz.nl/blog/arenas/