Maximizing the sum of the products of endpoints of edges in a graph Let $G$ be a graph with vertex set $V=\{v_1,v_2\dots v_n\}$ and edge set $E$. Let $f:V\rightarrow \mathbb [0,\infty)$ be a real valued function such that $\sum\limits_{i=1}^n f(v_i)=A$.
What is the maximum possible value for $\sum\limits_{uv\in E}f(u)f(v)$?
I remember seeing a sloppy proof a couple years ago that it was $\frac{A^2(k-1)}{2k}$ where $k$ is the clique number of $G$.
It is straightforward that this is a lower bound for the maximum, however I am having trouble proving it is the actual maximum. We can see it is a lower bound by taking a maximal clique and letting $f(v)=\frac{1}{k}$ if the vertex is in the clique and $0$ elsewhere.
 A: This is essentially the same proof as dream's, but formulated in a cool geometric way.
Let $A=1$ for simplicity. Let us label the vertices of $V$ as $1, 2, \ldots, n$, and let us denote the value of $f(v)$ by $x_v$. The problem then amounts to the optimization problem $\mathrm{OPT}(E)$ given by
$$\max_{x\in \triangle^n} P_E(x)$$
where $P_E(x)$ is the homogenous degree-2 polynomial $P_E(x) = \sum_{uv\in E} x_ux_v$ and where $\triangle^n$ is the standard $n$-simplex. For $x \in \triangle^n$, let the support of $x$ be the subset $S(x)\subseteq V$ defined by $u\in S(x)$ iff $x_u>0$. Let $M$ be the (nonempty) subset of $\triangle^n$ where $P_E(x)$ is maximized, and let $M^*$ be the subset of $M$ containing points of minimal support. Let $\ell_{uv}(x)$ denote the line through $x$ parallel to $\boldsymbol{e}_u - \boldsymbol{e}_v$. 
We claim that $S(x^*)$ is a clique for all $x^*\in M^*$. To see this, note that the directional gradient of $P_E(x)$ evaluated at some point $x$ lying on the line $\ell_{uv}(x^*)$, in the direction of $\ell_{uv}(x^*)$, is given by
$$\nabla P_E(x)\cdot(\boldsymbol{e}_u - \boldsymbol{e}_v) = \sum_{w\in N(u)} x_w - \sum_{w\in N(v)} x_w$$
for all $u,v\in S(x^*)$. If $(u,v) \notin E$, then this expression evaluates to a constant, since $x_w$ for $w\notin \{u,v\}$ is fixed for all $x\in \ell_{uv}$. But if it is a constant, then $\ell_{uv}\cap \partial \triangle^n$ would contain a point in $M$ of smaller support, contradicting the minimality of $M^*$. Thus $(u,v) \in E$ for all $u, v \in S(x^*)$, as claimed.
In fact, if $x\in M^*$, we demand that the directional gradient of $P_E(x)$  in the direction $\ell_{uv}(x)$ is $0$ for all $u,v\in S(x)$, since $x \notin \ell_{uv}\cap \partial \triangle^n$. Thus,
$$
0 = \nabla P_E(x^*)\cdot(\boldsymbol{e}_u - \boldsymbol{e}_v) 
= \sum_{w\in N(u)} x_w - \sum_{w\in N(v)} x_w
= x_v - x_u
$$
with the last equality following from the clique condition. This shows that the $x_u$ is a constant $\forall u \in S(x)$, and thus that $\mathrm{OPT}(E) = \frac{k'-1}{k'}$, where $k' = \lvert S(X) \rvert$. This quantity is maximized by taking $S(x)$ to be a maximal $k$-clique.
A: I managed to solve it with some help from fractal in AOPS.
For each function $f:V\rightarrow [0,\infty)$ with the desired properties let $pos(f)$ be $\{v\in V|f(v)>0\}$.
Now, consider the set of all such functions in $f$ such that $\sum\limits_{uv\in E}f(u)f(v)$ reaches the maximum-
Take $f$ to be one of functions in this set so that $|pos(f)|$ is minimal.
Suppose $pos(f)$ does not induce a clique, then there are vertices $a,b\in pos(f)$ which are not connected by an edge.
We can now write $\sum\limits_{uv\in E}f(u)f(v)=c_1+c_2f(a)+c_3f(b)$. Where $c_1$ is the sum of the products of the endpoints of all the edges that don't include $a$ or $b$, $c_2$ is the sum of $f(x)$ over all neighbours $x$ of $a$ and $c_3$ is the sum of $f(x)$ over all neighbours $x$ of $b$.
So basically, the edges not containing $a$ or $b$, plus the edges containing $a$ plus the edges containing $b$. So if we suppose $c_2\geq c_3$ then the function $f'$ defined as $f'(x)=f(x)$ if $x\neq a,b$ and $f'(a)=f(a)+f(b)$ and $f'(b)=0$ satisfies the following three conditions:
$\sum\limits(u\in V)f(u)  =A  $.
$\sum\limits_{uv\in E}f(u)f(v)\leq \sum\limits_{uv\in E}f'(u)f'(v)$.
$pos(f')<pos(f)$.
Contradicting the minimality of $|pos(f)|$.
So we can find a function that reaches the maximum and satisfies that $pos(f)$ induces a clique.
So now let $f$ be a function so that $pos(f)$ is a clique with vertex set $\{w_1,w_2\dots w_k\}$. Then we want to maximize:
$\sum\limits_{1\leq i<j\leq k}f(w_i)f(w_j)=\frac{(w_1+w_2+\dots w_k)^2-(w_1^2+w_2^2 + \dots + w_k^2)}{2}=\frac{A^2-(w_1^2+w_2^2 + \dots + w_k^2)}{2}$.
So we want to minimize the sum of squares, by Jensen's inequality or alternatively by AM-QM this occurs when $w_i=\frac{A}{k}$ for $1\leq i\leq k$. And in this case the desired sum becomes $\frac{A^2-k(A/k)^2}{2}=\frac{A^2(k-1)}{2k}$. Clearly this becomes larger as $k$ becomes larger, so the maximum is reached when $k$ is the clique number, as desired.
