1. (15 points) Imagine a knight sitting on an empty chessboard (8 by 8 squares). We...

Transcribed Image Text:

1. (15 points) Imagine a knight sitting on an empty chessboard (8 by 8 squares). We can model the knight's ability to move around the board by drawing a graph GK. This graph has one vertex for each square of the chessboard and two vertices are connected by an edge if and only if a knight placed on one of the corresponding squares can move to the other in a single jump. Although this graph is too big to draw by hand, we can still study it! (a) Draw a chessboard, then label each square with the degree of the corre- sponding vertex in GK. (b) How many vertices and edges are there in GK? (c) Let L be the length of the shortest non-trivial circuit (no repeated edges) in GK. What is L? (d) Is GK a planar graph? Prove your answer is correct. (e) What is the chromatic number of GK? Prove your answer is correct: what do we call graphs with this chromatic number? 1. (15 points) Imagine a knight sitting on an empty chessboard (8 by 8 squares). We can model the knight's ability to move around the board by drawing a graph GK. This graph has one vertex for each square of the chessboard and two vertices are connected by an edge if and only if a knight placed on one of the corresponding squares can move to the other in a single jump. Although this graph is too big to draw by hand, we can still study it! (a) Draw a chessboard, then label each square with the degree of the corre- sponding vertex in GK. (b) How many vertices and edges are there in GK? (c) Let L be the length of the shortest non-trivial circuit (no repeated edges) in GK. What is L? (d) Is GK a planar graph? Prove your answer is correct. (e) What is the chromatic number of GK? Prove your answer is correct: what do we call graphs with this chromatic number?

Answer rating: 100% (QA)

a The chessboard with the degrees of the corresponding vertices in GK labeled 23444432 34666643 4688... View the full answer