A security guard guards a grid of north-south and east-west paths around a bunch of cargo crates in neat lines and rows. He does a patrol route occasionally, subject to two rules;
a. he ends the route where he started;
b. he doesn't follow the same path twice.
So, if he has just one crate to guard, he walks north-east-south-west. Zero unguarded paths.
a 2 x 1 area is harder. north-east-east-south-west-west, one path is left unguarded.
2 x 2 might start at the middle; north-east-south-west-south-west-north-east. Or at a corner, 2N 2E 2S 2W, or some other route, but four paths are left unguarded.
So.. how many roads at left unguarded if the guard uses an optimal route around m lines x n rows of crates?
Let m<=n. If either m or n are even I think the answer is m+n. If both m and n are odd or m=1, m+n-2.
The corners all have 2 paths, the middle all have 4 paths, those on the perimeter but not on the corner have 3 paths. The problem occurs on the outer perimeter where three paths lead from an intersection (bridges of konigsberg type problem). So for every pair of three path intersections a path is left unguarded. So for an mxn grid there are 2(m-1) + 2(n-1) three paths. So halving this leaves m+n-2 unguarded paths.
However this solution works when m and n are odd (leaving an even number of paths not patrolled). In the case where m and n are odd you are forced to lose 2 corner paths on opposite corners which leaves m+n. In the case of m being odd and n being odd you lose 2 paths from adjacent corners again being m+n.
The one final case is where m=1. In this case you can walk around the outside and pair off the opposite awkward 3 junctions. This will be n-1 unguarded (equal to m+n-2 so no need to introduce yet a new formula).