Proving that every edge in a graph must belong to a $K_4$

Question

I've been asked to prove the following statement;

Let $G$ be a graph of order $n \ge 4$. Prove that if $\deg_G(v) \ge \frac{2n+1}{3}$ for every vertex in $G$, then every edge of $G$ belongs to a complete subgraph of order 4.

I'm really quite lost in even trying to begin this question. I was hoping to apply Turan's theorem, and use some manipulation of the binomial coefficients of this theorem, but I'm still not sure what I should be aiming for with this.

Any insights would be fantastic.

Answer 1

Hint: Let $(u,v)$ be an edge, and let $N(u)$ and $N(v)$ be the neighbours of $u$ and $v$ amongst $V(G)\setminus \{u,v\}.$ Show that $$\left|N(u)\cap N(v)\right|\geq \frac{n+2}{3}\geq 2.$$

Now, must there be an edge between two vertices in $N(u)\cap N(v)$?