# Construction of graph with given Wiener Index

Given the sum of weights of shortest paths between all vertices in a graph, how can I construct a connected graph that satisfies the given sum? That is, how can a graph with a given wiener index be created?

Consider the clique on $$n$$ vertices. Its Wiener index is $$\binom{n}{2}$$. Pick a vertex $$v$$ from the clique. Suppose we remove $$m$$ edges $$(x_1,y_1),\ldots,(x_m,y_m)$$ not adjacent to $$v$$. Since $$x_i,y_i$$ are connected via $$v$$, each edge we remove increases the Wiener index by one, and so the resulting Wiener index is $$\binom{n}{2} + m$$. The maximal number of edges we can remove is $$\binom{n-1}{2}$$, which corresponds to a Wiender index of $$\binom{n}{2} + \binom{n-1}{2} = (n-1)^2$$. We deduce that for every $$n$$, there are graphs having Wiener index $$\frac{n(n-1)}{2}$$ to $$(n-1)^2$$. Let's list these ranges for small $$n$$, starting with $$n = 2$$: $$[1,1], \; [3,4], \; [6,9], \; [10,16], \; [15,25], \ldots$$ Denoting the intervals as $$[a_n,b_n]$$, starting with $$n=5$$ we have $$a_{n+1} < b_n$$, which is not hard to check directly. Therefore, in this way we can construct graphs of any Wiener index other than $$2$$ or $$5$$.
It remains to rule out 2 and 5. First, note that a graph of $$n$$ vertices has Wiener index at least $$\binom{n}{2}$$. Since $$\binom{4}{2} = 6$$, it is enough to consider all graphs on at most 3 vertices: