Essentially the game is the same as removing edges from the graph formed from $n \times n$ squares as vertices and having edges connecting each two adjacent squares, and trying to keep the graph connected. This graph has $n^2$ vertices and $2n(n-1)$ edges; it becomes a tree, and no more edges can be deleted, iff there are $n^2 - 1$ edges left. So $n^2 - 2n + 1$ edges can be removed. This has the opposite parity from $n$, so the first player wins if $n$ is even, and the second player wins if $n$ is odd. It's optimal play just to always remove an edge that won't make yourself lose.