# Calculate the sum of pairwise distances in a regular circle graph

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!

-
And also: by "number of edges along shortest path" do you mean the number of times the shortest path intersects other edges in the graph? For example if $u,v$ are connected by a single edge in the graph, are you counting how many other segments in the graph cross the edge joining $u,v$ ? – coffeemath Nov 17 '12 at 21:27
@coffeemath, no, I mean the smallest number of edges that will lead from $u$ to $v$. For $u=v$ or any disconnected $u$ and $v$ (i.e. no path between $u$ and $v$), this distance is 0. – skyork Nov 17 '12 at 21:55
Just to make sure I get the definition: For n=11, k=4 (2 on each side) and a fixed vertex v there are four vertices at distance 1, four at distance 2, and two at distance 3 from v? Looks like an interesting problem! – coffeemath Nov 18 '12 at 1:08

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.