Q7 Matemática  (Simon Marais Mathematical Competition 2019)

Seja $G$ um grafo simples finito e seja $k$ o maior número de vértices de qualquer clique em $G$. Suponha que rotulemos cada vértice de $G$ com um número real não negativo, de modo que a soma de todos esses rótulos seja $1$. Defina o valor de uma aresta como o produto dos rótulos dos dois vértices em suas extremidades. Defina o valor de uma rotulagem como sendo a soma dos valores das arestas. Prove que o valor máximo possível de uma rotulagem de $G$ é $\frac{k-1}{2k}$. (Um grafo finito simples é um grafo com um número finito de vértices, no qual cada aresta conecta dois vértices distintos e duas arestas não conectam os mesmos dois vértices. Um clique em um grafo é um conjunto de vértices em que quaisquer dois são conectados por uma aresta .)