SIMON-MARAIS 2019 B3

Let $G$ be a finite simple graph and let $k$ be the largest number of vertices of any clique in $G$ . Suppose that we label each vertex of $G$ with a non-negative real number, so that the sum of all such labels is $1$ . Define the value of an edge to be the product of the labels of the two vertices at its ends. Define the value of a labelling to be the sum of values of the edges. Prove that the maximum possible value of a labelling of $G$ is $\frac{k-1}{2k}$ . (A finite simple graph is a graph with finitely many vertices, in which each edge connects two distinct vertices and no two edges connect the same two vertices. A clique in a graph is a set of vertices in which any two are connected by an edge.)