I have $n$ nodes arranged in a circle, and each node is connected to its nearest $k$ neighbors (i.e. $\frac{k}{2}$ on its left, and $\frac{k}{2}$ on its right) with $k$ being even.
The distance between any two nodes is measured by counting the number of edges along the shortest path between them.
My question is, how do I derive the formula (using $n$ and $k$) for the sum of the distances between all possible pairs of nodes in this graph? A breakdown of the derivation would be much appreciated!