Optimal insertion of edges for a graph
Let your vertex set be $\{v_1, \dots, v_n\}$.  If $n\leq5$, just add all possible edges.  Otherwise, create a new graph with vertices $\big\{v_{i,j}\mid i\in\{1, \dots, n\},\ j\in\{1, 2, 3, 4\}\big\}$, and edge set $\{v_{i,j}v_{k,\ell}\mid i\neq k\}$. You're looking for a minimum-weight perfect matching in that graph.  (Which is the same thing as a maximum-weight matching in the graph where you multiply all the costs by&nbsp;$-1$). This can be done in polynomial time, even though the graph isn't bipartite.