Linear programming maximizes the minimum distance problem
Let's first define some variables.

$$x_i \in \{0, 1\}$$
$$w_i \in \mathbb{Z}^+$$

Where $x_i=1\iff $ location $i$ is selected and $w_i$ equals the minimum distance from node $i$ to any selected city if $x_i=1$ and $\infty$ otherwise. We will use $D$ to represent $\infty$ and in practice $D$ can just be the diameter of the graph. We can constrain these variables below.

$$
\begin{align}
\sum_{i=1}^nx_i &amp;= k\\
w_i &amp; \leq \texttt{distance}(i,j) + D(2 - x_i - x_j)&amp; \forall j\neq i
\end{align}$$

It remains to find the minimum across all $w_i$. We will let this minimum be $y$. We constrain $y$ as follows
$$y \leq w_i \;\; \forall i$$

Now the objective function is clear, we want to find the largest $y$ that satisfies our constraints
$$\text{maximize }{y}$$

Our first constraint verifies that we select $k$ locations. The second gives us the minimum distance from a selected point to any other selected point. The third ensures that we find the minimum across these distances. Unfortunately, this is not a linear program but a mixed integer program.