A knight in chess is a piece that can move either two squares horizontally and one square vertically, or one square horizontally and two squares vertically. A knight's tour is a sequence of legal moves by a knight starting at some square and visiting each square on the chessboard exactly once. A knight's tour is called reentrant if there is a legal move that takes the knight from the last square of the tour back to the starting square. A well-known problem is to determine, given an m x n chessboard (that is, a chessboard with m rows and n columns), whether there exists a reentrant knight's tour. a. (5 points) Show how the knight tour problem can be modeled as a graph problem. Specify the vertices and the edges of the graph. b. (10 points) Show that there is a knight tour on a 3 4 chessboard. To do so, you need to describe the tour by listing the sequence of squares on the tour. You might find it convenient to use the standard labeling of a chessboard where the rows are labeled by the integers 1, 2, 3 and the columns by the characters a, b, c, d. A square is then referred to by a pair (x, y), where x is the row and y is the column determining the square. c. (5 points) Explain why there is no re-entrant knight tour on a 3 3 chessboard. 2. (15 points) A graph G is said to be a forest if G is a collection of trees, that is, if each connected component of G is a tree. Let G be a forest on n vertices, and suppose that G consists of a collection of k trees. What is the number of edges in G (in terms of n and k)? Justify your answer. 3. (20 points) For each of the following questions, either draw a graph with the given specifications or explain why no such graph exists: a. Acyclic graph with seven vertices and four edges. b. Tree with twelve vertices and fifteen edges. c. A graph that is not a tree with six vertices and five edges. d. A tree with five vertices and total degree 10. e. A connected graph with ten vertices and nine edges that contains a cycle. f. A simple connected graph with six vertices and six edges. g. A tree with ten vertices and total degree 24. Please refer to the figures given on the last page for the next 2 problems. 4. (15 points) Is the graph given in Figure 1 Hamiltonian? If so, list the vertices on a Hamiltonian cycle in order. 5. (15 points) Are the graphs given in Figure 2 isomorphic? If so, give an isomorphism between the two graphs. 6. (15 points) Is the graph given in Figure 2 planar? If so, give a planar drawing of the graph. How many faces does your drawing have? f k a d C f 3 Figure 1. Figure 2. n 3 2 6 5