I am looking at the random graph model $G(n,p)$ (i.e., the random graph on $n$ vertices where each edge appears independently with probability $p$).
A property of almost every graph is a property $A$ such that $\lim_{n \to \infty} \mathbb{P}(G(n,p)\text{ has } A) = 1$.
The question I wish to solve is the following: is it the case that for almost every graph, every vertex is contained in a triangle?
My attempt: I suspect that this is a property of almost every graph, because $G(n,p)$ has $\binom{n}{2}p \sim n^2p$ edges on average, which is much more than the number of edges you would need to have every vertex be in a triangle $(\leq 3n)$. It would suffice to prove the probability that some vertex is not in a triangle goes to zero. Call such a vertex a bad vertex. We have
\begin{align*}
\mathbb{P}(\text{there exists a bad vertex}) &\leq \mathbb{E}[\text{number of bad vertices}]\\
&= \sum_{v} \mathbb{P}(v \text{ is a bad vertex})\\
&= n \mathbb{P}(v\text{ is a bad vertex}).
\end{align*}
So I would need an upper bound on $\mathbb{P}(v\text{ is a bad vertex})$ that is $o(1/n$). So far I've been unable to come up with a useful bound. Any advice would be appreciated.
Best Answer
A given vertex is a member of ${n-1 \choose 2} \sim \frac 12n^2$ possible triangles. Each of them is realized with probability $p^3$ and the probabilities are (reasonably) independent, so the chance a vertex is bad is of order $(1-p^3)^{(\frac 12n^2)}$. The expected number of bad vertices is then $n(1-p^3)^{(\frac 12n^2)}$, which duly goes to $0$ as $n \to \infty$
If the failure of independence bothers you, partition the $n$ vertices other than the one we are considering into disjoint pairs and only consider triangles of one pair plus the vertex we are looking at. That certainly reduces the chance that we know our vertex is good, but changing the exponent to $\frac n2$ still supports the desired conclusion. For fixed $p$ almost every graph has every vertex in a triangle.