m by n grid graphs. An m by n grid graph represents...

m by n grid graphs. An m by n grid graph represents a rectangular street grid that is m blocks by n blocks, as indicatedin Fig. 6-57. (You should try Exercises 63 through 66 beforeyou try this one.)

(a) If m and n are both odd, then the m by n grid graph hasa Hamilton circuit. Describe the circuit by drawing iton a generic graph.

(b) If either m or n is even and the other one is odd, thenthe m by n grid graph has a Hamilton circuit. Describethe circuit by drawing it on a generic graph.

(c) If m and n are both even, then the m by n grid graphdoes not have a Hamilton circuit. Explain why aHamilton circuit is impossible.