# Point on a finite grid graph

Suppose we are on a finite 2D grid of points from $$(-a,-b)$$ to $$(a,b)$$. In the beginning, we are at the point $$(0,0)$$ inside the grid. How many points are there that have distance $$k$$ between $$(0,0)$$?

Are you asking how many vertices have distance exactly $$k$$ from $$(0,0)$$?

If so, the answer is $$4k$$ for any $$k$$ which is at least one, and less than or equal to $$\min\{a,b\}$$.

You can check this inductively.

Look at how the vertices at distance 2 in the grid branch out from those at distance 1. The three red vertices in quadrant 1 ($$x \geq 0$$ and $$y \geq 0$$) are all adjacent to the two blue vertices in quadrant 1. A similar pattern holds in all four quadrants.

So let our inductive hypothesis be that the number of vertices at distance $$k$$ from (0,0) in any single quadrant is $$k+1$$. (This is true for $$k=1$$, so we have a base case).

Now let's prove it for distance $$k+1$$. Let's first assume we are in the first quadrant. Each vertex at distance $$k$$ (of which there are k+1 by assumption) has exactly 1 neighbour, directly above it, at distance $$k+1$$. But, there is also one extra neighbour. The vertex at distance $$k$$ on the x-axis has a neighbour at distance $$k+1$$ directly to the right (see the figure below, the 'extra' neighbour to the right has a little + next to it). Thus in quadrant 1, there are $$k+2$$ vertices at distance $$k+1$$ from (0,0).

This proof works for the other quadrants by 'rotating' the argument, as shown in the figure below. This completes the proof by induction that each quadrant contains $$k+1$$ vertices at distance $$k$$ from $$(0,0)$$.

Note that the vertices on the axes get double-counted, as they lie in two quadrants. We know each quadrant has $$k+1$$ vertices at distance $$k$$, and there are 4 quadrants, with 4 vertices double-counted, so the total number of vertices at distance $$k$$ is $$4(k+1) - 4 = 4k$$.

• Thank you for your answer. But I want to know when we are on the finite grid, like when we're in the middle of the grid graph $P_n \box P_m$. Do we have any ways to find how many points that have distance $k$ from where we are? – Nuttanon Apr 28 '20 at 9:46
• Because of symmetry (everywhere on the inside of the grid looks the same), this answer works anywhere on the grid, except if you are distance less than $k$ from one of the boundaries. If you are near the boundaries, that's a lot messier =/ – Brandon du Preez Apr 28 '20 at 13:47
• I just wondering that is there any function that will depend on 3 variables n, m, and k to find the total number of vertices at distance $k$. – Nuttanon Apr 28 '20 at 16:18