Show ex$(n, H)\leq \left\lfloor\frac{n^2+n}{4}\right\rfloor$

58 Views Asked by At

Let $H$ be the graph on $4$ vertices with $5$ edges.

Show ex$(n, H)\leq \left\lfloor\frac{n^2+n}{4}\right\rfloor$.

You have to use that $\sum_{uv\in E(G)}d(u)+d(v)=\sum_{v\in V(G)}d(v)^2$.

I know that for connected vertices $u$ and $v$, $d(u)+d(v)\leq n+1$ since they share at most one neighbor. But I don't know how to continue.

1

There are 1 best solutions below

0
On BEST ANSWER

Note that for any two adjacent vertices $u$ and $w$ we have $d(u) + d(w) \leq n + 1$ (otherwise $G$ would contain a copy of $H$), and so \begin{align*} \sum_{e = uw \in E} (d(u) + d(w)) \leq e(G)\cdot (n+1). \end{align*} On the other hand, the sum counts the degree of $v$, once for each neighbor of $v$, so it is also equal $\displaystyle \sum_{v \in V} d(v)^2$. Thus, by Cauchy-Schwarz, we have \begin{align*} \frac{1}{n} \left(\sum d(v) \right)^2 \leq \sum_v d(v)^2 \leq e(G)\cdot (n+1), \end{align*} but, by Euler's degree sum formula, we also have $\displaystyle \frac{1}{n} \left(\sum d(v) \right)^2 = \frac{1}{n} 4 e(G)^2$. Thus, \begin{align*} \frac{1}{n}4 e(G)^2 \leq e(G)\cdot(n+1) \Rightarrow e(G) \leq \frac{n(n+1)}{4}, \end{align*} as desired. Notice that this is exactly the proof of Mantel's Theorem but with $n + 1$ replacing $n$ where it makes sense to.