It can be done with an array of lists, i.e.
var map = new List<int>[number of nodes];
Each list would represent the ids of the nodes that each node connects to. The list in position 0 would be the connections for node 0, etc. As nodes are cut, you remove the appropriate values from the list.
A custom class also works, though you'd still need a way to look at a particular node quickly. You can judge for yourself whether the extra code is worth it.