Maximum possible edge betweenness of a graph? Betweenness, roughly speaking, measures how many times a particular node or edge in a graph is part of the shortest path, when counting paths among all pairs of nodes.  For nodes, it's easy to see that a star graph forces the central node to have a maximum betweenness as it lies between every pair of nodes.
I'm trying to determine if there exists a graph such that a particular edge is on every shortest path (and therefore has maximum edge betweenness).  Obviously, for an undirected graph, there are a maximum of $\frac{n(n-1)}{2}$ shortest paths.  But considering some small examples, I was unable to design a graph such that any edge actually achieved this max.  Is such a (weighted) graph possible (by proof or construction), or can we find the actual maximum betweenness?
My use case is normalizing these edge betweenness scores.  I could just use the number of shortest paths (which is what networkx and I suspect other implementations do), but if we can figure out what the actual max is (or some demonstrable estimates), I'd like to use that.
Edit: To clarify, I'm considering a weighted graph (possibly with zero weights allowed, though practically that's less interesting).  But analyzing an unweighted graph may of course still be helpful.
 A: Suppose that a shortest path from vertex $v$ to vertex $w$ in the graph uses edge $xy$: let's say the path goes $(v, \dots, x, y, \dots, w)$. Then distances from $v$ are strictly increasing along the path, and distances from $w$ are strictly decreasing: in particular, $d(v,x) < d(v,y)$ and $d(w,x) > d(w,y)$.
This means that all shortest paths using edge $xy$ must start at a vertex closer to $x$ than to $y$, and end at a vertex closer to $y$ than to $x$. If there are $n_x$ vertices of the first type, and $n_y$ of the second, then at most $n_x \cdot n_y$ pairs of vertices have a shortest path using edge $xy$.
With the constraint $n_x + n_y \le n$ and $n_x, n_y \ge 0$, $n_x \cdot n_y$ is maximized at $\lfloor \frac{n^2}{4}\rfloor$ when $n_x = n_y = \frac n2$ (for even $n$) or when $\{n_x, n_y\} = \{\frac{n-1}{2}, \frac{n+1}{2}\}$ (for odd $n$).
This bound is achievable for all $n$, by letting $xy$ be the only edge between two connected subgraphs, one with $n_x$ vertices and one with $n_y$ vertices.
