If degree of each vertex of a graph is big then each its edge belongs to $K_4$ Let G be a graph of $n \geq 4 $
Prove that if $\delta (G) \geq \frac {2n+1}{3} $ then every edge of G belongs to a complete sub-graph of order 4.
Also show that for infinitely many values of $n\geq 4 $ there exists a graph G such that  $\delta (G) \geq \frac {2n}{3} $ and some edge of G does not belong to a complete sub-graph of order 4.
I started by saying that there is some vertex v with minimal degree consider a vertex u that v is connected to that is also minimal degree. now assume that there is no neighbour of both u and v but the degree remaining is $ \frac {2n+1-3}{3} + \frac {2n+1-3 }{3} = \frac {4n-4}{3}  > n-2$  does this implie that there is a third vertex y that is connected to both u and v ?
 A: Let $e$ be an arbitrary edge of $G$ and $V’$ be the set of the vertices adjacent to both endvertices of $G$. It is easy to check that $\delta(G)\ge\frac{2n+1}3$ implies that $|V’|\ge\frac{n+2}3$. If there are no adjacent vertices in $V’$ than each vertex of $V’$ has degree at most $n-|V’|\le \frac{2n-2}3<\frac{2n+1}3$, a contradiction. Now any two adjacent vertices from $V’$ together with the endvertices of $e$ constitute a vertex set of the required graph $K_4$.
The above proof also shows a way to construct the required family of counterexamples. For any positive integer $k$ let $G’$ be a complete graph on vertices $\{v_1,\dots,v_{3k-2}\}$, but without the edges of the complete graph on vertices $\{v_k,\dots,v_{2k-1}\}$. The graph $G$ is created by adding to $G’$ vertices $v_{3k-1}$ and $v_{3k}$ connected by an edge $e$ and making $v_{3k-1}$ adjacent to the vertices $\{v_1,\dots,v_{2k-1}\}$ and $v_{3k}$ adjacent to the vertices $\{v_{k},\dots,v_{3k-2}\}$. It is easy to see that $n=|V(G)|=3k$, $\delta(G)\ge 2k=\frac{2n}3$, but the edge $e$ is not contained in any copy of the graph $K_4$.
