In a simple graph with $n$ vertices and $m$ edges, if $m>\frac12n\sqrt{n+1}$ then the graph has a cycle of length $3$ or $4$ 
Let's assume $G$ is a simple graph, having $n$ vertices and $m$ edges. What I want to prove is that if $$m > \frac12 n \sqrt{n+1}$$ then $G$ includes at least a cycle of length 3 or 4 (triangle or square).

Note: What I've tried is to make proof by contradiction, assuming there is a vertex $v$ being included in no square or triangle, but have not resulted in anything useful yet.
 A: In fact, an even tighter bound holds:

A graph of girth at least five with $n$ vertices has at most
$\frac{1}2n\sqrt{n-1}$ edges.

The following proof is taken from page 8, theorem 2.2 in the following paper:

Extremal graphs of girth five, Lazebnik et al (1993)
http://www.math.udel.edu/~lazebnik/papers/techrep.pdf

Preliminary definitions:
-The girth of a graph is the length of the shortest cycle that it contains.
-The diameter of a graph is the maximum distance between any two vertices.
-Call a graph $G$ extremal if it has girth at least five and there does not exist any other graph of girth at least five with the same number of vertices and strictly fewer edges.
Lemma 1: Every extremal graph has diameter at most three.
Proof of lemma 1: Let $x,y$ be vertices of distance at least four in an extremal graph. Then adding the edge $xy$ to the graph would produce another graph of girth five.
Let $D_i$ be the number of unordered pairs of vertices whose distance is at most $i$ and $d(x)$ be the degree of the vertex $x$.
Lemma 2: In any girth of girth at least five, $D_2=\sum_{x\in V(G)}\binom{d(x)}2$
Proof of lemma 2: Let $y,z$ be one of the $\binom{d(x)}2$ pairs of vertices adjacent to $x$. If $y$ were adjacent to $z$, we would have a triangle. If $y,z$ were also adjacent to some $x'$ then we would have a four-cycle.
Main statement: Any extremal graph has at most $e=\frac{1}2n\sqrt{n-1}$ edges.
Proof of main statement:
From the lemmas, $\binom{n}2=D_1+D_2+D_3=e+\sum_{x\in V(G)}\binom{d(x)}2+D_3$.
Let $\overline{d}$ be the average degree of the graph and $\sigma^2=\sum_{x\in V(G)}(d(x)-\overline{d})^2$. Obviously $2e=\sum_{x\in V(G)}d(x)$ and $\overline{d}=2e/n$.
Then $\sum d(x)^2=\sigma^2-\sum \overline{d}^2-2\sum d\overline{d}=\sigma^2+4e^2/n$.
So $\binom{n}2=\sigma^2/2+2e^2/n+D_3$. If we take $\sigma^2=D_3=0$ then we get the desired upper bound on $e$.
A: I'll present perhaps a "friendlier-looking" (though that is a matter of personal opinion) proof of the same statement that Angela pursues in their answer above; it isn't better, just a different presentation that you may prefer. Be warned, however -- you will have to fill-in some blanks for yourself along the way.
Proposition. Let $G$ be a graph of order $n$ and size $m$. If $m > \frac{1}{2}n\sqrt{n-1}$, $G$ has girth at most $4$.
Proof. Consider the number $\sum_{v \in V(G)}\binom{deg(v)}{2}$; it counts the number of triples of vertices $v_1, v_2, v_3$ such that $v_1$ is a neighbor of both $v_2$ and $v_3$ (why? Reading Angela's proof of lemma 2 will help). Under the assumption that $G$ hasn't any $3$- or $4$-cycles, we can obtain the inequality $$\sum_{v \in V(G)}\binom{deg(v)}{2} \leq \binom{n}{2} - m$$ quite easily (any pair of adjacent vertices has no common neighbor (else a triangle) and no pair of nonadjacent vertices has $\geq 2$ common neighbors (else a $C_4$)). If you prefer it in words, we are "bounding the number of common neighbors of a given pair of vertices."
To obtain the sharpest bound possible, we wish to minimize the number $\sum_{v \in V(G)}\binom{deg(v)}{2}$. As always, we're working with the Handshaking Lemma's constraint of $\sum_{v \in V(G)}deg(v) = 2m$, and we can easily observe that $\sum_{v \in V(G)}\binom{deg(v)}{2}$ is minimized by taking $deg(v) = 2m/n$ for each $v$ (sample some alternative ways to distribute the degrees to convince yourself of this fact). From here, it's all algebra; we have the inequality $$n(\frac{m}{n})(\frac{2m}{n-1}) \leq \frac{n(n-1)}{2} - m$$ which eventually simplifies to $$m \leq \frac{1}{2}n\sqrt{n-1},$$ the desired contradiction. $\square$
Remark. Of course, this proves something stronger than your desired statement. I couldn't think of an inequality which works out to be exactly what's given in your question, but it's quite possible that there is a more elementary method which proves your weaker result (which would probably be the method which the person who wrote the question had in mind).
