Maximal possible edges in graph

Question

A graph has 20 vertices. If two vertices are of same degree, they are not connected by an edge. Find the maximal possible number of edges in such a graph

I tried constructing it through diagram but am getting 1 vertex of 19 degree and rest of the vertices of other degree but am not able to proceed further. My approach is to find the number of vertices with degree satisfying the above condition and then using the handshaking lemma but am unable to proceed.

Can you please suggest some hints on the same?

Answer 1

I am not sure that this is true, but let us assume that in an optimal solution, every vertex is adjacent to every other vertex of a different degree. So the optimal solution might be a complete $k$-partite graph with no two partition classes of the same size.

I made a computer search to find the repetition-free partition $20=n_1+\cdots +n_k$ that maximizes

$$|E|=\sum_{i<j} n_i n_j,$$

since this is the number of edges of the resulting graphs.

The result is $K_{2,3,4,5,6}$ is optimal with 155 edges.

---

Just in case you wonder, I used the following (quite unreadable) Mathematica code

MaximalBy[
    { #, Plus @@ Times @@@ Subsets[#,{2}] } & /@ 
        Select[IntegerPartitions[20],DuplicateFreeQ],
    Last
]

With output {{{6,5,4,3,2},155}}.

Answer 2

It turns out that $155$ is not the maximum. Via integer linear programming, I found that the maximum is instead $156$, attained by graphs with degree sequences $$(19,18,18,17,17,17,16,16,16,16,15,15,15,15,14,14,14,14,14,12),$$ $$(19,18,18,17,17,17,16,16,16,15,15,15,15,15,14,14,14,14,14,13),$$ and $$(19,18,18,17,17,17,16,16,16,16,15,15,15,15,14,14,14,14,13,13),$$ and perhaps others.