# Dividing a complete graph into two cliques with maximal sum of edge weights

Problem: Considering a complete weighted graph $$G$$ with $$n$$ vertices, where $$n\in2\mathbb Z$$ is an even number, remove edges in such a way that you end up with two cliques of graph $$G$$, each having $$\frac n2\in\mathbb Z$$ vertices, and the sum of all weights is maximized.

Example:

$$\begin{bmatrix} &A & B & C & D\\ A &0 &1 &0.66 &0.5\\ B &1 &0 &0.01 &0.5\\ C &0.66 &0.01 &0 &0.33\\ D &0.5 &0.5 &0.33 &0 \end{bmatrix}$$

The above adjacency matrix of graph $$G$$ is an instance of the problem with $$A$$, $$B$$, $$C$$ and $$D$$ being the vertices of the graph. In this instance, the solution to the problem is pairing $$A$$ with $$B$$ $$(1)$$ and $$C$$ with $$D$$ $$(0.33)$$, with the resulting weight sum $$1.33$$ being the maximum achievable value.

What would be the exact algorithm for solving this problem, or maybe there is a problem which it can be reduced to?

I'm going to assume you didn't mean to end up two (maximal) cliques, but instead two disconnected complete graphs. Those are not the same, e.g. for $$n = 6$$ you can end up with extra edges that don't form any other maximal cliques otherwise: 