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!
Best Answer
Consider a fixed vertex $v$, and suppose $n-1=kq+r$ with $0 \le r <k$ (that is, $r$ is the remainder on dividing $n-1$ by $k$, and $q$ is the quotient.
Then there are $k$ at distance 1 from $v$, another $k$ at distance 2, and so on, up to a final $k$ at distance $q$ from $v$, and the remaining (if any) $r$ are at distance $q+1$ from $v$. This gives the total contribution from $v$ as $$k(1+2+...+q)+r(q+1)=k\cdot q(q+1)/2 +r(q+1).$$
Since there are $n$ vertices the above must be multiplied by $n$ for the final sum.
EDIT: perhaps this answer has to be divided by 2, since it counts each distance between say $v$ and $w$ twice.