# Grid graphs eliminating edges

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$$?

• "On a $3 \times 3$ grid, on a corner vertex, I can still only remove 1 edge" - that's incorrect. You can remove at least 3 edges (all but one edge adjacent to the central node). Mar 31 at 23:39
• @Dmitry youre right i just misinterpreted the problem, i was finding the minimum number of edges I could remove not the maximum
– user904870
Mar 31 at 23:41

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.
• so for my $3 \times 3$ hypothetical, I can remove 4 edges: 3 from the center vertex and one from an edge surrounding?
• Yes, and moreover you don't have to be careful when you do it. As long as you don't immediately make the graph disconnected you can keep going until only $|V|-1$ edges remain (where $|V|$ is the number of vertices). In fact there are various theoretical results which can help you. Try to look at theorems that give various analogous definitions for trees. Mar 31 at 23:47