This question inspires another:
With four states in proximity to each other one often sees five boundaries between states; for example: $$ \begin{array}{rc} 1 &\text{New York}/\text{Vermont} \\ 2 &\text{New York}/\text{Massachusets} \\ 3 & \text{New York}/\text{Connecticut} \\ 4 & \text{Connecticut}/\text{Massachusetts} \\ 5 & \text{Massachusetts}/\text{Vermont} \\ \\ &\text{but not Vermont}/\text{Connecticut} \end{array} $$ With four states one can see six boundaries only if one of them is surrounded by the other three.
With five states in contiguity, the smallest number of boundaries you can have is four; and the largest is less than ten even though there are ten unordered pairs, because they must lie in a plain.
With $n$ states, the smallest is $n-1.$
- With $n$ states, what is the largest number of state boundaries you can have? (Taking each state to be a connected set in the plane.)
- Is there any sense in which it makes sense to ask about an average number, choosing the boundaries of states in some random way?
- Is this function of $n$ found in OEIS?
Assume all your states are connected, and consider the dual graph: vertices are the states, and edges connect states the share a border. You're in effect asking for the largest number of edges possible in a planar graph with $n$ vertices, which turns out to be $3(n-2)$. (In short, planarity requires that $V - E + F = 2$, and counting the edges around a face gives $E\geq \frac{3}{2}F$. There's a straightforward example in the other direction.) As for randomization, there is an entire field known as random graph theory that addresses this kind of problem.