Q: Let $G=(V,E)$, such that $|V|=n$. G does not contain as a sub-graph a $K_{2,m}$ - complete bipartite graph which one side contains 2 vertices, and the second $m$ vertices. Prove that that the number of edges must obey the inequality: $|E|\leq \frac{(m-1)^{1/2}\cdot n^{3/2}}{2}+\frac{n}{4}$
My solution:
Let: $x\in V \text{ so } \Gamma(x)=\{y:\{x,y\}\in E\}$
G does not contain $K_{2,m}$ so for any $x_1,x_2\in V$: $|\Gamma(x_1) \cap \Gamma(x_2)|<m$ Define: $\binom{\Gamma(x)}{m}=\{\{z_1,z_2,...,z_m\}:z_i \in \Gamma(x), \forall i , 1\geq i\leq m\}$ Thus: $\binom{\Gamma(x_1)}{m}\cap \binom{\Gamma(x_2)}{m}=\varnothing$ Moreover: $\left|\binom{\Gamma(x)}{m}\right|=\binom{deg(x)}{m}$ and because:
$\binom{\Gamma(x_1)}{m}\cap \binom{\Gamma(x_2)}{m}=\varnothing$ we can infer: $\sum_{x\in V} \binom{deg(x)}{m}=\left| \bigcup_{x\in V} \binom{\Gamma(x)}{m}\right|\leq \binom{n}{m}$
$\phi(deg(x))=\binom{deg(x)}{m}, \phi \text{ is convex.} \to \frac{1}{n} \sum_{x\in V} \phi(deg(x))$
$\geq \phi \left(\frac{1}{n} \sum_{x\in V} \phi(deg(x))\right)$
$\frac{1}{n} \binom{n}{m} \geq \frac{1}{n} \sum_{x \in V} \binom{deg(x)}{m} \geq \binom{\frac{1}{n} \sum_{x \in V} deg(x)}{m}=\binom{\frac{2|E|}{n}}{m}$
$\frac{1}{n} \binom{n}{m} \geq \binom{\frac{2|E|}{n}}{m}$
I don't know how to proceed, or maybe the question need to be solved differently. Thanks to anyone who can help!
We shall look at the following sum:
$\sum_{x\in V} \binom{deg(x)}{2}$
We'll bound it:
Now apply the pigeon-hole principle:
Holes: $\binom{n}{2}$ distinct pairs of vertices - $\{v,w\}$
Pigeons: Number of pairs with the same adjacent vertex. Every distinct vertex counts. $\#(u,\{v,w\}): v,w\in \Gamma(u)$
If there are $(m-1)\binom{n}{2}+1$ pigeons, so there must a be a hole with $m$ pigeons. We can not allow that. Thus, $pigeons \leq (m-1)\binom{n}{2}$.
Count the pigeons:
#pigeons = Number of pairs with the same adjacent vertex.
#pigeons = Sum all over all vertices. For each vertex we'll count every pair of adjacent vertices. That is exactly: $\sum_{x\in V} \binom{deg(x)}{2}$.
Thus: $\sum_{x\in V} \binom{deg(x)}{2}\leq (m-1)\binom{n}{2}$
The function $f(x)=\binom{deg(x)}{2}$ is convex so:
$\binom{\sum_{x\in V} deg(x)}{2}\leq(1/n) (m-1)\binom{n}{2}$
$\binom{2|E|/n}{2}\leq (1/n)\frac{n(n-1)}{2}$
$\frac{(2|E|/n)(2|E|/n-1)}{2} \leq \frac{(n-1)(m-1)}{2}$
$(4/n^2)|E|^2-(2/n)|E|-(n-1)(m-1)\leq 0$
Quadratic equation: $\frac{2/n \pm \sqrt{4/n^2-(16/n^2)(m-1)(n-1)}}{\frac{8}{n^2}}$
$|E|\leq \frac{n}{4}+\frac{\sqrt{0.25n^2+n^2(m-1)(n-1)}}{2} \leq \frac{n}{4} +\frac{(m-1)^{1/2}n^{3/2}}{2}$
$\blacksquare$