= Triangle with an attached leaf in a binomial random graph
Partition the vertices into two sets of comparable size. If $np\to\infty$, the first set contains a triangle with probability tending to one. Conditional on any triangle chosen using only internal edges, the probability that none of its vertices has a neighbour in the second set is at most
$$
(1-p)^{3\lfloor n/2\rfloor}
\leq e^{-3p\lfloor n/2\rfloor}\longrightarrow0.
$$
Hence $G(n,p)$ contains a triangle with an attached leaf with probability tending to one.
Back to article page
