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

  • $\begingroup$ "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). $\endgroup$
    – Dmitry
    Mar 31 at 23:39
  • $\begingroup$ @Dmitry youre right i just misinterpreted the problem, i was finding the minimum number of edges I could remove not the maximum $\endgroup$
    – 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.

  • $\begingroup$ so for my $3 \times 3$ hypothetical, I can remove 4 edges: 3 from the center vertex and one from an edge surrounding? $\endgroup$
    – user904870
    Mar 31 at 23:44
  • $\begingroup$ 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. $\endgroup$
    – Yorch
    Mar 31 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy