2
$\begingroup$

In chess, a knight's move consists of two spaces either vertically or horizontally, followed by one space in the perpendicular direction. In this way, every knight's move results in an L shaped displacement from the original position. To model all of the legal knight's moves on an n x n chessboard, we can create a graph where each vertex represents a square on the board, and two vertices are adjacent if an only if a knight can legally move between the corresponding squares. Use the handshake lemma to determine the number of edges in GK_n

  • Is GK_n always, sometimes or never Eulerian

  • Does GK_n always, sometimes or never contain an Euler trail

By use of the Handshake Lemma edges are twice the amount of degree sum so if you had a graph GK_4 with 16 vertices, it would have degree sum 48 and 24 edges. I'm not sure how to use this information to determine the number of edges in GK_n. The abstractness is what confuses me.

$\endgroup$
  • $\begingroup$ If the abstractness is confusing, try drawing a small portion of the graph $GK_N$. $\endgroup$ – Austin Mohr May 13 '13 at 0:47
  • 2
    $\begingroup$ Hint: What is the degree of, say, the vertex on square a2 on a chessboard? How many such vertices are there? $\endgroup$ – Henning Makholm May 13 '13 at 0:49
2
$\begingroup$

Instead of the handshake Lemma, you can use the more general principle of Double Counting.

We can split up the knight's moves into those of the form $ (2, 1), (2, -1), (1, 2), (1, -2) $. There are clearly $ (n-1) (n-2)$ of each move, and hence a total of $ 4 (n-1)(n-2)$ edges in the graph.

$\endgroup$
1
$\begingroup$

HINT: You need to know the number of odd vertices. Squares that are at least two rows and two columns away from the edges of the board have degree $8$: they're all even. What about squares along the edges of the board, or one row or column in? Be a little careful: they're not all the same.

$\endgroup$
1
$\begingroup$

If I was going to do this problem (find the number of edges in the graph), I'd look at the small cases, and find a formula for the number of vertices of each degree. (There will be some small cases which need to be handled separately.)

So, let's take a look at the $5 \times 5$, $6 \times 6$, and $7 \times 7$ graphs:

5x5 knight's graph

6x6 knight's graph

7x7 knight's graph

(I've ascribed the vertices with their degrees.)

E.g. for $n \geq 3$, there will always be $4$ vertices of degree $2$ (the four corner vertices). I would find such formulae for the number of vertices of degrees $3,4,6,8$, and argue that degrees $1,5,7$ are impossible.

To make it formal, we'd need to ensure that every square was accounted for. Depending on how much formality is required, an argument might also be presented as to why each square has a given degree.

Once we have a formula for the number of vertices of each degree, we can use the Handshaking Lemma to find the number of edges.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy