Suppose we have an $n \times n$ grid. Let $G$ be its equivalent graph representation, which has $n^2$ vertices and an undirected edge drawn between vertices $u$ and $v$ if and only if their corresponding grid squares are adjacent (diagonal doesn't count). Since there are at most $4$ edges per vertex, the number of edges in $G$ is $\mathcal{O}(n^2)$.
Consider removing $s$ vertices (and any respective edges) from $G$. It's trivial to say that the number of edges is still $\mathcal{O}(n^2)$. However, can we get a tighter upper bound?
My current guess is that removing $s$ vertices removes $\mathcal{O}(s)$ edges, so is the solution simply $\mathcal{O}(n^2 - s)$? I'm not quite sure if this is a correct bound.
Edit: I assume since we're subtracting, to find a tighter upper bound we need to find a tight lower bound on the negative portion (in this case the number of edges we remove). Could it be correct to say that showing the number of vertices removed is $\Omega(s)$ implies that the number of edges remaining is $\mathcal{O}(n^2 - s)$?
If you remove $s$ vertices, then we count the number of edges removed as follows:
We start with $2s$ edges, consisting of, for each vertex, the edge emanating upwards from that vertex, and the edge emanating to the right.
This does not account for all edges. Namely, for each vertex $v$ which was removed such that the vertex below $v$ was not removed, there will be an edge removed from the bottom of $v$ that was not counted in the previous bullet. I will call this a "downward external edge". Similarly, you need to add in the "leftward external edges".
Finally, there was some over-counting in the first bullet point. Any vertex on the top edge does not have an edge emanating upward. To correct for this, we can subtract the number of vertices on the top border. Similarly, we must subtract the number of vertices on the right border.
Putting this altogether,
$$ \begin{align} \text{# edges removed} &= 2s+\text{# downward external edges}+\text{# leftward external edges}\\ &\qquad\;-\text{# vertices on top border}-\text{# vertices on right border} \end{align} $$
This proves that $$ 2s-2n\le \text{# edges removed}\le 4s $$ so $$ 2n(n-1)+2n-2s\ge \text{# edges remaining}\ge 2n(n-1)-4s $$