Successive addition or deletion of vertices (or edges) in graph

Question

I am trying to perform a kind of dynamic graph simulation where vertices and edges of graph are added and deleted according to the current state of the graph at each time step. I know that there are built-in functions such as EdgeDelete or VertexAdd which seem to do this job.

However, if I understand correctly, what these functions do is constructing a new graph object instead of modifying the existing graph g so something like g = VertexDelete[g,b] involves O(N) time complexity instead of O(1) which is too expensive for such tasks.

Even though I understand that this kind of simulation is best done by other programming languages, I am wondering if there exists a kind of (design) pattern to do such things.

If the situation is too general, maybe one easy example might be constructing a certain graph g and randomly removing a vertex each time recording the size of the giant cluster size. Currently my solution would be g = VertexDelete[g, randomVertex[g]], given the assumption that we have a function randomVertex[g].

First of all, is my understanding about the graph functionality true? If yes, what is the best way to implement such dynamical graph simulation?

--EDIT--

Following the comment, I tried to perform a benchmark measuring the time spent from a sample code presented below run on my old slow machine.

n = 4 10^3;
g = RandomGraph[ {n, 2 n}];
Timing[( g = VertexDelete[ g, #]; ) & /@ RandomSample[ Range[n]]  ][[1]]

After getting time from various sizes I could get the following plot which indicates the time complexity is around O(N^2). If I did not make a mistake, it shows VertexDelete is a costly operation!!