An integer lattice graph can be defined as a graph such that and , i.e., two vertices are adjacent when exactly one of their co-ordinates differ by while the other co-ordinates are all equal. It is a particularly easy graph to visualize. It is 2n-regular. [Clearly, given a vertex, to get one of its neighbours, you have to change exactly one of the co-ordinates. You may either increase it by or decrease it by and this may be done for all n co-ordinates. Thus, there are neighbours for every vertex.]
It becomes a bit more interesting when you consider the finite integer lattice graph. As you can guess, the vertex set is now defined by , where is a +ve integer. The edge set has the same definition. This graph, while still quite easy to visualize is no longer regular. And this makes way for an interesting problem:
Find the average degree of a finite integer lattice graph.
How do we do this? Well, it is clear that the interior points still have degree . However, everything changes for the points whose co-ordinates have at least one or .
We have to tackle this part carefully. Let . Let be the number of co-ordinates whose absolute value is not . Then, . To find the degree of , we have to find out the number of neighbours of . To go to a neighbour from , we have to change exactly one of the co-ordinates as before. For the co-ordinates which are strictly between and , we can either increase or decrease by as before. However, for the other co-ordinates, we can only decrease by (when the co-ordinate is ) or increase by (when the co-ordinate is , but we cannot do both. So, now we can obtain a neighbour of in ways. Hence, .
Is this enough? No. Just the degree won’t do. We also need to know the exact number of vertices of each degree between and . How many vertices can have exactly co-ordinates equal to or and the remaining not equal to ? The answer is clearly [Note that there are possibilities for each co-ordinate].
Then, we have
Hence, the average degree of the graph is .
That was interesting, wasn’t it? The result isn’t very surprising if you try putting .
Phew! I am literally sick and tired of writing now. The next such post will be at least a week later.
Acknowledgements: Prof Young, who gave this problem in an assignment