MathDB

Let

G

be a ﬁnite 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

. Deﬁne the value of an edge to be the product of the labels of the two vertices at its ends. Deﬁne 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

\frac{k-1}{2k}

. (A ﬁnite simple graph is a graph with ﬁnitely 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.)

Problem Statement