CLAIM: m = n are the only integers such it is possible for the table to have an Eulerian cycle It is well known that it is equivalent for every point to have an even degree for it to have an Eulerian cycle. At m = n, we have a construction (Image 1) It is sufficient to show 1) m and n have the same parity and 2) m, n do not differ by greater than 2 to show m must equal n. Lemma 1) m and n have the same parity Proof: Color each unit square according to a regularly colored chessboard (alternating white, black). WLOG, m is even, n is odd. Call a point"cringe" if it initially (without adding diagonals) has an odd degree. There are n-1/2 cringe black points and n-3/2 cringe white points in the first row of the table and n-3/2 cringe black and n-1/2 cringe white points in the bottom row of the table, and there are m-2/2 cringe black and m-2/2 cringe white points in the first and last columns of the table. In total, there are n+m-4 cringe black or cringe white points in total. HOWEVER, the number of cringe black (or white) points must be even, as otherwise we cannot have all vertices have a degree of 2, since black and white points cannot be connected through a diagonal. Lemma 2) m and n differ by less than 2 If m and n are odd and even respectively, we are done by lemma 1 Otherwise, assume WLOG that m >= n + 2. Then there are at least 2 cringe points in the first and last columns of the table that must have a path made up of only diagonals through them to the other side. (Note that if we CANNOT have 2 cringe points in the first/last rows of that are connected by a path of diagonals as this would intersect a path from 2 cringe points in the first and last columns of the table, leading to a contradiction) Therefore, each cringe point in the first or last rows must be connected to a cringe point in the first or last column of the table, to prevent contradiction we must have each of these cringe points corresponding IN THIS WAY (depends on parity of m,n, see Image 2/3) , otherwise we have two diagonals intersecting within a unit square. (This is true as if we have a path of only diagonals connecting two points on the same row/column we cannot have the degree of all points being even) If m, n are even, note that if we color points again in the same way (white, black), we have for each point in the first column, the corresponding point in the same row but in the last row has an opposite color, therefore we must have at least 2 of the paths of diagonals must intersect. If m, n are odd, we must have an arrangement of diagonals including THIS (see Image 3), as otherwise, the first and last rows would have a different number of unconnected cringe points, forcing a connection of cringe points in the same column, which. It is clear that in this arrangement, must have two diagonal paths must intersect. By contradiction, we have m, n must differ by at most 1, and by the parity condition we must have m = n.

It is well known that a graph has an Eulerian cycle if and only if all vertices have even degree. Let $G$ be the graph consisting only diagonal edges, and call a vertex $\emph{strange}$ if it is on a side of the grid but is not a corner. Then all strange vertices have degree $1$ in $G$, and all other vertices have even degree. Claim: the set of strange vertices can be partitioned into pairs $(u_1,v_1)$, $(u_2,v_2), \dots, (u_k,v_k)$ such that there exists a path from $u_i$ to $v_i$ for all $1\le i\le k$, and these $k$ paths are disjoint. Proof: fix a strange vertex $u$, and walk along edges of $G$ until we are stuck (i.e. we are at a vertex $v$ such that all edges incident to $v$ have already been walked on). Then $v$ must be strange, so we can remove the path between $u$ and $v$ from $G$ and repeat this process $k-1$ times. Define $P_i$ as the path between $u_i$ and $v_i$. For any $i$, $P_i$ divides the remaining strange vertices into two sets -- let $f(i)$ be the magnitude of the smaller of these two sets. Now, color the vertices of the grid black and white in a checkerboard pattern. Then for all $1\le i\le k$, $u_i$ and $v_i$ are the same color. The condition on diagonals implies that no path between two black vertices can cross a path between two white vertices. Claim: for all $1\le i\le k$, $u_i$ and $v_i$ lie on different sides of the grid. Proof: Assume the contrary, and choose the $i$ with $f(i)$ minimal such that $u_i$ and $v_i$ lie on the same side of the grid. Let $S$ be the set of vertices between $u_i$ and $v_i$ on that side of the grid. WLOG let $u_i$ and $v_i$ be black. Then by the minimality of $f(i)$, any white vertex in $S$ is paired with a white vertex not in $S$ -- a contradiction and the claim is proved. Claim: either $m = n$ or for all $1\le i\le k$, $u_i$ and $v_i$ do not lie on opposite sides of the grid. Proof: assume the contrary -- that $m\neq n$ and there exists some $i$ such that $u_i$ and $v_i$ lie on opposite sides of the grid. Let $S_1$ and $S_2$ be the sets of strange vertices on either side of $P_i$. Note that $|S_1|$ and $|S_2|$ are both odd. WLOG let $u_i$ and $v_i$ be black and lie on the top and bottom sides of the grid, respectively. We have two cases. Case 1: there are an odd number of white vertices in $S_1$. Then at least one of these vertices must be paired with a white vertex in $S_2$, and we have a contradiction. Case 2: there are an odd number of black vertices in $S_1$. Then at least one black vertex $u$ in $S_1$ must be paired with a black vertex $v$ in $S_2$. If either $u$ or $v$ lies on a vertical side of the grid, then $P_i$ and the path between $u$ and $v$ will "box in" at least one white strange vertex, forcing a contradiction to the previous claim. Hence, $u$ and $v$ lie on the left and right sides of the grid (in some order). Now consider the four quadrants into which $P(i)$ and the path between $u$ and $v$ divide the grid. In any one of these quadrants, the number of white strange vertices on the vertical side must equal the number of white strange vertices on the horizontal side. In particular, the total number of white strange vertices on the top and bottom sides of the grid equals the total number of white strange vertices on the left and right sides of the grid. From here, quick casework on the parities of $m$ and $n$ is enough to conclude that $m = n$, so we have a contradiction and the claim is proved. Now, the claim implies that the total number of strange vertices on the top and bottom sides of the grid equals the total number of strange vertices on the left and right sides of the grid. This immediately implies $m = n$, as desired. Finally, we have the following construction for $m = n = 6$ which generalizes readily for all $m = n$.