# How do i solve this graph theory problem?

"A sheet has a height (h) of at least 2 and a width (w) of at least 2. There are (w)x(h) tiles on the sheet. A valid path is one that moves adjacent to the current tile (forward, backwards, left, right, but not diagonal). Show that if either w or h is an even number, then there exists a path (P) that touches every single tile exactly once and ends up at the same tile it started at. Then prove that if both w or h is odd, then this path (P) can not exist."

I'm stumped. I'm not sure how to prove this. I have drawn it out and can see that it holds, but i'm not sure how to prove it generally for any number of w and h. We are told not to use induction on this question, and that was the only method i was thinking could work. Any help would be greatly appreciated.

HINT: When at least one of $w$ and $h$ is even, there is a systematic way to traverse the sheet; try to generalize from this example, in which the bullet points represent square of the sheet.
$$\begin{array}{|c|c|c|} \hline \bullet&\to&\bullet&\to&\bullet&\to&\bullet\\ \uparrow&&&&&&\downarrow\\ \bullet&&\bullet&\leftarrow&\bullet&&\bullet\\ \uparrow&&\downarrow&&\uparrow&&\downarrow\\ \bullet&\leftarrow&\bullet&&\bullet&\leftarrow&\bullet\\ \hline \end{array}$$
For the odd case, imagine coloring the squares alternately black and white, like a checkerboard. Each move must go from a square to a square of the other color. If $w$ and $h$ are both odd, and the square in the upper lefthand corner is white, how many white squares are there? How many black squares?
• @Team.Coco: No, because the traversal is possible even when only one of the dimensions is even. The route that I used in the $3\times 4$ example above really does generalize to all sheets with at least one even dimension. Try it first with even widths: start in the upper lefthand corner, go across the top, and then try to generalize what I did. When you have that down, you can go to even heights; that requires turning the pattern sideways. – Brian M. Scott Oct 26 '16 at 19:05
• @Team.Coco: The case in which one dimension is $2$ is a special case that has to be handled separately, but it’s also completely trivial, since you can simply loop around the sheet. What I did generalizes to all sheets with an even dimension $\ge 4$. – Brian M. Scott Oct 26 '16 at 19:15