Problem

Source: Simon Marias MC 2019 B3

Tags: college contests



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.)