# Sum of the shortest paths in graph

Let $d_{G} \left(x,y \right)$ be the length of the shortest path between the vertices $x$ and $y$ in graph $G$ and let $s\left(G\right) = \sum_{x,y \in V \left[G\right]} d_{G} \left(x,y \right)$ . For which undirected, 2-connected n-vertex graphs $G$, value $S(G)$ is the highest?

-
A cycle seems like it would be hard to beat, but I have no proof. –  Ross Millikan Mar 31 '12 at 15:09
It seems that s(G) = 2W(G) where W is the Wiener Index of a graph mathworld.wolfram.com/WienerIndex.html I am sure this problem was already studied somewhere. –  Jernej May 8 '12 at 16:19

It's a cycle, assume there is another graph $G$ which is not cycle and has maximal sum as desired, It has some nodes like $v$ with degree more than two and its degree is minimal (by this condition). $v$'s neighbors are $x_1,x_2,...x_r$ we show them by $N_1(v)$, Also $v$ is on some cycle like $C$, because $G$ is two connected, assume neighbors of $v$ on $C$ are $x_1,x_2$, now if you move $x_2,x_3,..,x_r$ on $C$ and create $C'$ by: $x_1,v,x_2,x_3,...,x_r,...,x_1$ and let other connections be same, newly created graph is two connected, because there is two way between interior vertices of $C'$, also by our construction we didn't affect outer vertices connection, we just replaced an edge with path. Also $G'$ has bigger sum of shortest path, because again we didn't decreases length of a path between vertices of $O = G\backslash (C\cup N_1(v))$, Also we didn't change the length of a paths between vertices in $O$ and $N_1(v) \cup C$, but length of a shortest path between $v$ and $x_3$ increased (by 1). So new graph $G'$ has bigger sum of shortest paths, but this contradict with our assumption. So $G$ can't have a vertex of degree more than 2. and because it's two connected, it's a cycle.