# $K_3$ subgraph in a random graph

Consider a random graph of $n$ vertices where the probability of there being an edge between any two vertices is .01. I want to see what is the asymptotic behavior of the probability that there exists a cycle of length 3 within this graph. I understand that the number of ways I can have a cycle of length 3 is $\binom{n}{3},$ and the probability of their being a cycle between a given set of 3 vertices is $(.01)^3.$ However, I am not quite sure where to go with this particular probability. Any assistance will be greatly appreciated.

• I think the probability distribution is irrelevant all such graphs are isomorphic. – Rene Schipperus Jan 5 '16 at 2:34
• It is a lot easier to find the expected number of triangles. – Jorge Fernández Hidalgo Jan 5 '16 at 2:37
• Possible duplicate of Expected number of triangles in a random graph of size $n$ – JMoravitz Jan 5 '16 at 3:55
• @JMoravitz: Isn't the expected number of triangles, found in that earlier question, easier to compute (by linearity of expectation) than the probability of at least one triangle? Such I take to be the significance of dREaM's Comment. – hardmath Jan 5 '16 at 4:06

First I guess your random graph model is usually indicated with $G(n,p)$, which is called a Binomial Random graph with $n$ vertices and each edge is selected independently with probability $p$.
If $n\geq 3$ then the probability that a random graph G(n,0.01) contains $C_3$ as an induced subgraph is positive, let's say it is $r>0$. Since $V(G)$, the vertex set of $G$, contains $\lfloor \frac{n}{3} \rfloor$ disjoint subsets of $3$ vertices each, the probability that no induced subgraph of G is isomorphic to $C_3$ is at most $(1-r)^{\lfloor \frac{n}{3} \rfloor}$ which tends to $0$ as $n \rightarrow \infty$.
Hence as $n \rightarrow \infty$, almost every graph $G(n,0.01)$ contains $C_3$ as a induced subgraph.