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.)
Problem
Source: Simon Marias MC 2019 B3
Tags: college contests
16.10.2019 11:37
Cleanest solution I heard: consider two vertices not connected by an edge. Then the value of the labelling is a linear function in those two vertices and so its maximal value are at the extreme points $\implies$ we can smooth them such that one of the vertex has value $0$. Then we can proceed by induction and so the only case left is a complete graph which is straightforward.
16.10.2019 11:45
fattypiggy123 wrote: Cleanest solution I heard: consider two vertices not connected by an edge. Then the value of the labelling is a linear function in those two vertices and so its maximal value are at the extreme points $\implies$ we can smooth them such that one of the vertex has value $0$. Then we can proceed by induction and so the only case left is a complete graph which is straightforward. You don't need to induct. By compactness maximum value is achieved, pick the tuple attaining the max value with max number of zero terms. Then by similar argument the vertices with nonzero values forms a clique, after which it's easy. @below Yeah but I like this more
16.10.2019 11:52
Yea well that is pretty much the same
04.06.2020 20:24
Suppose $G $ cannot be partition into $n $ connected component $C_1,C_2,\hdots,C_n.$ Each component has the sum its label are $v_1,v_2,\hdots,v_n $ respectively. From this hypothesis $\sum v_i=1, $ for each $v_i , 0\le v_i\le 1(\clubsuit)$ Let $S $ denotes the value of labelling of the graph. $S_i, i=1,\hdots,n $ is the value of labelling of $C_i. $ Observe that $S=\sum S_i (\clubsuit). $ Because each vertices has non-negative value, $S_i\le\sum_{i,j}(a_i\cdot a_j) $with $a_i,a_j $ are $2$ weight values, assigned for $2$ vertices of $C_i $($i,j $ both are vertex of $C_i $). If $C_i $ is a complete graph, then $S_i $ obtains the maximum value, when $C_i $ is a clique of $G.$ By AM-GM inequality $S_i\le\sum a_ia_j\le\left(d_i\frac{(d_i-1)}{2}\right)*\left(\frac {\sum a_i}{d_i}\right)^2=\frac {(d_i-2)}{2d_i}*v_i^{2} $ where $d_i $ is the size of clique $C_i (\heartsuit)$ Maximum value of $S_i $ is accompanied when each $a_i $ has the same value. We obtain $S\le\sum\left (d_i\frac {(d_i-1)}{2}\right)*v_i^{2}(\bullet) $ From the hypothesis $d_i\le k\implies\frac {(d-1)}{d}\le \frac {(k-1)}{k}\implies S\le\frac {(k-1)}{2k}\sum v_i^{2} $ From $(\clubsuit) $ $v_i^{2}\le v_i\implies S\le\frac {(k-1)}{2k}\sum v_i=\frac {(k-1)}{2j}$ Equality holds when the clique has all the vertices, which has same value $=\tfrac 1k. $
26.03.2022 05:46
Firstly, we prove the result for a $k$-clique. Let the labellings be $x_1,x_2,...,x_k$. Thus, the labelling has value $$\sum_{1\leq i < j \leq k} x_ix_j=\frac{(\sum_{i=1}^k a_i)-\sum_{i=1}^k a_i^2}{2}=\frac{1-\sum_{i=1}^k a_i^2}{2} \leq \frac{1-\frac{1}{k}}{2}=\frac{k-1}{2k}$$by Cauchy-Schwarz, with equality attained when all the labellings are equal to $\frac{1}{k}$. $(\star)$ Now, given a graph $G$, let $L(G)$ be the value of its labelling. Since the label of each vertex is a non-negative real number, when we add an edge on $G$, obtaining a graph $G'$, $L(G') \geq L(G)$. Thus, we keep adding edges to $G$ until the moment we have a graph $H$ such that if we add any edge on $G$, $G$ will have a $(k+1)$-clique. Hence, $H$ is the equality case of a graph without $(k+1)$-clique, so by Turán's Theorem, we know that $H$ is a complete $k$-partite graph. Let $H=A_1 \cup A_2 \cup... \cup A_k$ such that for all $a_i \in A_i, a_j \in A_j$, $a_ia_j$ is an edge. Thus, if we let $s_i$ to be the sum of the labels in $A_i$, we have that the labeling of $H$ is $\sum_{1 \leq i <j \leq k} s_is_j$, and $s_1+s_2+...+s_k=1$, and from $(\star)$, we know that such value is at most $\frac{k-1}{2k}$. Therefore, $L(G) \leq L(H) \leq \frac{k-1}{2k}$, as desired. The equality is attained when every vertex in the $k$-clique has label $\frac{1}{k}$ and the other vertices have label equal to $0$. This clearly works. $\blacksquare$