Application of Jensen’s inequality in graph.

82 Views Asked by At

This is a step in a proof that I don’t get. I’m paraphasing the argument here. Please give an explanation for the last statement.

Suppose $G$ is a graph on $n$ vertices, and $G$ contains a $K_r(q)$, i.e. a complete $r$-partite graph, with each of the partitions $U_1, \dots, U_r$ containing $q$ vertices. A claw with center $x$ in $G - K_r(q)$ is a set of $rs$ edges incident to $x$, such that precisely $s$ edges join $x$ to each of the $U_i$’s (picture below).

If there are at least $(r-1)qn + D$ edges between $K_r(q)$ and $G - K_r(q)$, where $D > sn + 2qn^{1 - \frac{1}{s}}$, then there are at least $n {q \choose s}^{r-1}{{D/n} \choose s}$ claws in $G$ by Jensen’s inequality.

enter image description here

In the picture above the edges in bold indicate that the $r$-partite graph is complete.

Also, since I can’t verify the formula above, I’m unable to determine whether the claws that are counted are only those with centers in $G - K_r(q)$, or also those with centers in $K_r(q)$.