I have an $m \times n$ grid graph. I'm trying to find the maximum number of edges I can remove from the graph such that two vertices can still be connected in some roundabout way.
I know the total number of edges in a grid graph is $2mn – m – n$
I drew this out using a $2 \times 2$ grid and found I could only remove $1$ edge.
On a $3 \times 3$ grid, on a corner vertex, I can still only remove $1$ edge.
Is the maximum number of edges I can remove just $1$?
Best Answer
In general for any connected graph with $m$ edges and $n$ vertices it is possible to remove $m-(n-1)$ edges without disconnecting it. This is because if the graph has more edges it will contain a cycle, and any edge in the cycle can be removed.
In your case the number of edges is $(m-1)n+(n-1)m =2mn-m-n$ and the number of vertices is $nm$. Therefore you can remove $mn-m-n+1$ edges.