Let $\left\{\mathbf{p}\_1,\dots, \mathbf{p}\_k\right\}$ be a set of points in $n$-dimensional Euclidean space, and let the second moment of these points be defined as: 


$
U=\sum \limits\_{i=1}^{k} ||\mathbf{p}\_i -\bar{\mathbf{p}}||^2,
$


where $\bar{\mathbf{p}}$ is their centroid.


Let two points $i$ and $j$ be connected if $||\mathbf{p}\_i - \mathbf{p}\_j||\leq \lambda$. 


Then, under the constraint that the points are to form a connected graph, what is the configuration that maximizes their second moment? 



Maximum Dispersion of a Connected Geometric Graph
Notice that this is the same as maximizing $\sum\_{i<j} |p\_i-p\_j|^2$. Also by rescaling assume that $\lambda =1$. Since your graph is connected there is a spanning tree whose vertices are the $p\_i$'s. Let $\text{d}(i,j)$ denote the graph theoretic distance between $p\_i$ and $p\_j$ along this tree. From the triangle inequality $\sum\_{i<j} |p\_i-p\_j|^2 \le \sum\_{i<j} \text{d}(i,j)^2$. It is a nice combinatorial exercise to show that this last quantity is maximized when the tree is a path. Therefore your second moment is maximized when the points are all on a line so that $|p\_1-p\_2|=|p\_2-p\_3|=\cdots=|p\_{k-1}-p\_k|=1$.


