Let $G(n,p)$ denote the Erdős–Rényi random graph, where $n$ is the number of nodes and $p$ is the probability for each edge. I'm interested in precisely what range of $p$ the random graph has at least one edge not contained in any triangle.
One easily checks that if $$p \ge \left( \frac{2 \log n + \omega}{n} \right)^{1/2}, $$ where $\omega \to \infty$ arbitrarily slowly, then every pair of vertices is a.a.s. connected by a path of length $2$, so it follows that every edge is contained in a triangle.
This can be sharpened though. Let $X$ denote the expected number of edges not in any triangle.
Then $$E[X] = {n \choose 2} p (1-p^2)^{n-2},$$ and if I did my calculation correctly, then if $$p \ge \left( \frac{(3/2) \log n + (1/2) \log \log {n} + \omega}{n} \right)^{1/2}$$ then there are a.a.s. no edges not contained in any triangles, since $E[X] \to 0$ as $n \to \infty$.
My guess is that this inequality is more-or-less sharp. What I'd like to show then is that if $p$ is much smaller, then there are a.a.s. edges not contained in any triangle.
Suppose for example that $$p \ge \left( \frac{(3/2) \log n - C \log\log{n} }{n} \right)^{1/2}.$$ Is it true that for large enough constant $C>0$ we have a.a.s. that at least one edge not contained in any triangle? The expected number of such edges is tending to infinity as a power of $\log{n}$, but obviously that's not enough.
I have tried using Janson's inequality, for example, but I am stuck because the events I am trying to count are not pairwise independent even though they are "almost independent."
