A graph has 45 vertices. If two vertices are of the same degree, they are not connected by an edge. Find the maximal possible number of edges in such a graph.
I have tried many different methods but not able to get it correct. Tried 2,3,4,5,6,7,8,9 as a partition, but obviously making a mistake. Can someone please help with it?
Finally understood the solution. The following approach is working, although still does not make sense 100%. Never the less, the example graph is constructed as follows:
45 = 1 + 2 + ... + 9,
and we split the vertices into 9 groups and draw edges only between vertices of different groups.
The total edges are calculated between each combination.
1*(45-1) + 2*(45-2) + 3*(45-3) + ... + 9*(45-9) = 2|E|
which gives a total number of edges as:
|E| = 870