Key Concepts. Graphs (definitions, modeling problems using graphs), Hamiltonian paths and cycles, Eulerian paths and cycles, Fleury's algorithm.

4. Let m, n be positive integers and define G_m,n to be the grid of mn vertices arranged in m rows and n columns such that each vertex has an edge to the vertices to the left, right, above, and below it, if such vertex is available.

(a) For what value of n that G₃,n has an Eulerian path? An Eulerian circuit? Explain.

(b) Show that if m and n are odd, then Gm,n doesn't have a Hamiltonian cycle.