Let $r\geq 4$ and let $\delta (G)> (1-\frac{1}{r-1})|G|$. Show that every edge is contained in a $K_r$ Let $r\geq 4$ and let $\delta (G)> (1-\frac{1}{r-1})|G|$. Show that every edge is contained in a $K_r$
Hint: Pick the remaining vertices of the $K_r$ one by one.
I'm at a loss as to what to do, usually i'd approach something like this with induction but with this I'm lost.
 A: This is not an answer but the comments are not long enough.
Perhaps induction is the way to go. Consider the following ideas (they just convey that $G$ contains a $K^r$ which is a start): We see $1 - \frac{1}{r-1} = \frac{r-2}{r-1}$.
Induction start with $r = 3$ (and not $r = 4$):
It is well-known (?) that: If $|E(G)| > \frac{1}{4} \cdot |V(G)|^2$, then $G$ contains a triangle. 
We know $2 \cdot |E(G)| = \sum_{v\in V(G)} d_G(v)$ and so $\delta(G) > \frac{3-2}{3-1}\cdot |V(G)| = \frac{1}{2}\cdot |V(G)|$ implies $|E(G)| = \frac{1}{2}\cdot\sum_{v\in V(G)} d_G(v) \geq \frac{1}{2}\cdot\sum_{v\in V(G)} \delta(G) > \frac{1}{4}\cdot |V(G)|^2$, that is, $G$ contains a triangle. Now we have to show that every edge lies in a triangle (your job).
Induction step with $s > 3$: Note that $s > r$ implies $\frac{s-2}{s-1} > \frac{r-2}{r-1}$, that is, if $\delta(G) > \frac{s-2}{s-1}\cdot |V(G)|$, then $G$ contains a $K^r$ by induction hypothesis for $r < s$. Now we have to show that $G$ contains even a $K^s$ and that every edge lies in such a $K^s$ (your job).
Perhaps you can take it from here.
