1. The problem statement, all variables and given/known data Consider a grid with height p >= 2 and width q >= 2, so there are pq squares in the grid. A valid walk on the grid is a walk that starts on one square and subsequently moves to adjacent squares (you cannot move diagonally). Define a tour to be a valid walk on the grid that touches each and every square exactly once and begins and ends on the same square. First show that if either p or q is even then there exists a tour. Prove that if p and q are odd, there does not exist a tour. 2. Relevant equations No idea. 3. The attempt at a solution No induction. I have no idea how to go about this proof. I would love some guidance on how to get started.