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.
Best Answer
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.