Upper bound on number of edges for graph with no C3 or C4

76 Views Asked by At

$G$ is a simple graph having $n$ vertices and $m$ edges. Show that if G has girth $\ge$ 5, then $$m \le \frac12 n \sqrt{n-1}$$.

***I am required to use a particular method: i.e. show first that $\sum_{w \in N(v)} d(w) \le n-1$, N(v) being the neighbor of any vertex in $G$. Then use this fact and $(\sum_{w} d(w))^2 \le n*\sum_{w} d(w)^2$ by cauchy's thm to show the result.

I got the first part but I am having trouble showing the second part using its result.

My thinking is as follows: $\sum_{w \in N(v)} d(w) \le n-1$ implies $\sum_{v \in G} \sum_{w \in N(v)} d(w) \le n*(n-1)$, since $\sum_{v \in G}$ means counting n times. We also have $\sum_{x\in v} d(x)=2m$ so $(\sum_{x\in v} d(x))^2=4m^2$.

Cauchy Schwarz gets. $(\sum_{w \in N(v)} d(w))^2 \le n*\sum_{w \in N(v)} d(w)^2$

I am kind of stuck here and don't really know how to use the above things I derived to get the result. Any help is appreciated thanks.