Arestas máximas possíveis no gráfico

Question

Um gráfico possui 20 vértices. Se dois vértices são do mesmo grau, eles não são conectados por uma aresta. Encontre o número máximo possível de arestas em tal gráfico

Tentei construí-lo por meio de um diagrama, mas estou obtendo 1 vértice de 19 graus e o resto dos vértices de outro grau, mas não consigo prosseguir. Minha abordagem é encontrar o número de vértices com grau que satisfaça a condição acima e, em seguida, usar o lema do aperto de mão, mas não consigo prosseguir.

Você pode sugerir algumas dicas sobre o mesmo?

Answer 1

Não estou certo de que isso seja verdade, mas vamos supor que, em uma solução ótima, cada vértice é adjacente a todos os outros vértices de um grau diferente. Portanto, a melhor solução pode ser um completo$k$- gráfico de partições sem duas classes de partição do mesmo tamanho.

Eu fiz uma pesquisa no computador para encontrar a partição livre de repetição $20=n_1+\cdots +n_k$ que maximiza

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

uma vez que este é o número de arestas dos gráficos resultantes.

O resultado é $K_{2,3,4,5,6}$ é ideal com 155 arestas.

---

Caso você esteja se perguntando, eu usei o seguinte código (bastante ilegível) do Mathematica

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

Com saída {{{6,5,4,3,2},155}}.

Answer 2

Acontece que $155$não é o máximo. Por meio da programação linear inteira, descobri que o máximo é, em vez$156$, obtido por gráficos com sequências de graus $$(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),$$ e $$(19,18,18,17,17,17,16,16,16,16,15,15,15,15,14,14,14,14,13,13),$$ e talvez outros.