4

I have to prove that the formula $4n^2-12n+8$ gives the number of edges on a knight graph, where n is the number of vertices horizontally and vertically and n^2 is the number of vertices.

I've proved it for $n=4$ (the smallest possible value of $n$ with which the knight graph works) and I've assumed that the result is true for n=k but where do I go from here? How do I prove it works for $n=k+1$?

  • Proof by induction confuses me immensely so any help is appreciated. –  Oct 28 '13 at 20:30
  • Your question could be more clear. Does $n$ mean that you have a n x n chessboard? – Sid Oct 28 '13 at 20:37
  • Oh, yes, sorry. I'll add that in. –  Oct 28 '13 at 20:38
  • Note that the question says nothing about a knight tour, just a graph of knight moves; the formula is still valid for $n=3$ (where it gives 8 edges, which you can easily see to be correct: two edges from each corner square to the two opposite sides of the square). Consider: when you go from a $n\times n$ chessboard to a $(n+1)\times(n+1)$ board (say, by adding a row along the top and a column along the right), how many new edges get added? – Steven Stadnicki Oct 28 '13 at 20:43
  • However, a 3 by 3 chessboard cannot form a complete graph as the centre vertex lacks and edge. As for how many edges are added, well, I can envisage that (corners have 2 moves, adjacent ones have 3, all others have 4) but I wouldn't know how to express it algebraically. –  Oct 28 '13 at 20:48
  • Whether the graph is 'complete' (in the sense of hitting all squares or not - note that this isn't what's meant by a 'complete graph') is moot; I really want to emphasize again that you're not looking at tours here, just at the graph whose vertices are the squares and whose edges are the knight moves. That a vertex (square) has no edges to it doesn't affect anything in the problem. – Steven Stadnicki Oct 28 '13 at 21:30
  • @StevenStadnicki is quite right, as I showed in the last paragraph in my answer to this problem, the formula is valid for all cases when $n \ge 1$. The question whether there exist vertices with no neighbours is not relevant. – Sid Oct 28 '13 at 21:43

2 Answers2

2

The idea of induction is that given your answer for n=k, you can show that the same holds (in this case that the number of edges equals 4n^2-12n+8) for n=k+1.

To show this we must look at the number of edges that are added when you take a chessboard of k+1 x k+1 instead of k x k. So lets add a new row and column below and left of the old kxk board. I call this the new board. From the corners of this board you have 2 knight moves to the old board (and ofcourse 2 from the old board to these corners, but as we are counting edges and not moves we will only look at moves starting on the new board). The spaces next to the edges each have 3 options. All other new spaces have 4 options.

So the extra number of edges looks to be 3*2 (for the corners) + 4*3 (for the spaces next to the corners) + 2*((k+1)-4)*4 (for all other new spaces) = 6+12+8(k-3)=8k-6.

Note however that from the spaces next to the lower right corner you can also make a move to spaces on the new board, i.e. we counted them double. Therefore we have to substract 2 from the above answer.

Adding this all together; The new board containts all the moves the old one had + 8k-8 extra moves. I.e. 4k^2-12k+8 + 8k-8 = 4(k+1)^2-12(k+1)+8

Dorien
  • 36
2

Instead of solving the problem by induction, we can simply calculate the number of edges using our knowledge of how the knight moves. We consider six cases on a n x n chessboard when $n \ge 4$. To make the visualization easier, I have uploaded a picture of an 8 x 8 chessboard.

enter image description here

a) The knight is in the corner. When the knight is located in the corner, it can move to two different squares. There are four corners, so we will have $4 \cdot 2 = 8 $ edges.

b) The knight is located on a square on the edge of the board next to the corner. Here, the knight can move to three squares. As there are $8$ such squares (two next to every corner), we will have $8 \cdot 3 = 24$ edges.

c) The knight is located on the edge of the board but not on the squares in a) or b). Here, the knight has access to 4 squares. As there are $(n-4) \cdot 4$ such squares, we get $(n-4) \cdot 4 \cdot 4 = 16(n-4)$ edges.

d) The knight is on one of the squares that is adjacent to the corner but not on the edge. Here, the knight can move to $4$ squares, and there are $4$ such squares, so we have $4 \cdot 4 = 16$ edges.

e) The knight is on the row or column that is next to the row or column that's on the edge of the board, but not on the squares in d) or b). There are $(n-4) \cdot 4$ such squares and on each such square the knight can move to 6 squares, so we get $(n-4) \cdot 4 \cdot 6 = 24(n-4)$ edges.

f) The knight is on any other square, that is the squares that are not the two first or two last columns or the two top or two bottom rows. There are $(n-4) \cdot (n-4)$ such squares and on each such square, the knight can move to 8 squares, giving us $8 \cdot (n-4)^2$ edges.

Now we just calculate the sum of the edges in a) - f). Since we counted each edge twice, our answer will be half of this sum:

$\frac{16+24+16(n-4)+16+24(n-4)+8(n-4)^2}{2} = 4n^2 - 12n + 8$

Note: Incidentally, the answer is also valid for $n \ge 1$. For $n=1$ and $n=2$, the formula will give us the answer $0$, which is true since a knight on a 1 x 1 and a 2 x 2 chessboard has access to no squares, hence the corresponding knight graphs have no edges. A knight graph for the 3 x 3 chessboard is a disconnected graph with the circle graph $C_8$ and a lone vertex as components. The formula will give us that this graph will have $8$ edges, which is quite true.

Sid
  • 4,372