Intuition on inequality in proving a bound on the sum of squares of degrees of a graph

Question

Given a simple connected graph $G$ with $n$ vertices and $m$ edges, let $d_1, ..., d_n$ denote the degrees of the vertices of the graph. In this very short paper, the author prove the inequality

$$\sum_{i\in G} d_i^2 \leq m\left(\frac{2m}{n-1}+n-2\right)$$

The main thrust is when the author introduce and prove the following magical inequality for any set of reals $\{x_{ij}\}$:

$$\frac{n-1}{2}\sum_{i}\left(\sum_{j\neq i}x_{ij} \right)^2 \leq \left(\sum_{ij}x_{ij} \right)^2 +{n-1 \choose 2} \sum_{ij}x_{ij}^2$$

By simply letting $x_{ij}=1$ if $\{i,j\}$ is an edge in $G$ and $0$ otherwise (i.e indicator for edges), the above inequality rearranges to the first desired inequality.

Now, if I am given inequality $2$, I can easily 1) prove it and 2) conclude the inequality 1. However, I am left for words on how the author could've came up with inequality $2$ in the first place. Can someone shed a light on some intuition on where it might have originated from.

Answer 1

Let's see.

The first thing is to generalize the vertex degree in a simple graph to the weight in the edge weighted graph, which is not an issue in terms of inventiveness. Now just look at what is given and what is required to be bounded in these terms. You'll get the sum on the left but now you need to count the edges somehow to make sure that when all $x_{ij}\in\{0,1\}$, you have equality with your expression. Since everything is quadratic, both the sum $\sum_{ij}x_{ij}^2$ and $\sum_{i,j}x_{ij}$ (squared in the inequality) come as natural choices. It is not clear enough which one should really be used, so you throw in both (this is the general rule, BTW: if you are not sure whether to put potatoes or carrots into the soup, put the mixture in a free proportion to be chosen later). Thus, you desire an inequality $$ A\le\beta B+\gamma C $$ with known and not too difficult to understand quadratic forms $A,B,C$. Now you just figure out for what $\beta$ and $\gamma$ it holds and then optimize the parameters to get the result suitable for your purposes.

Exercises (for you).

1. Find all admissible pairs $(\beta,\gamma)$.

2. Generalize this technique for the sum of cubes (cubic forms are less pleasant to deal with, but you are not required to get the optimal bound, just something decent; let's say you are allowed to be twice off but no more).

Once you do both, you'll see all the magic clearer than I :-)

Answer 2

I can not say for the author, but if you use the variables $x_{ij}\in \{0,1\}$ with 1's corresponding to edges (that is pretty standard, see "adjacency matrix of a graph"), then your inequality 1) reads as 2), if you additionaly want it to be homogeneous in $x_i$'s, which is also quite a natural desire.