Skip to main content
1 of 2
MR_BD
  • 550
  • 5
  • 18

Expected Number of edges for a graph to have a Triangle?

i want to compute the expected number of edges for a graph to have some triangles (loop with length 3)


i just solved a similar simpler problem:

Generate a random graph on $n$ vertices and probability $p$ for existence of each edge... what is the expected number of triangles? it will be $\frac{(np)^3}{6}$

with some calculus you can derive that if the number of edges is greater than $\frac{n\sqrt[3]6}{2}$ the expected number of triangles is greater than One.

but the Original problem is much harder than this case, However i think it must be some relation between the answer of these two problem. (is there?)

the question is How to solve the Original Problem?


i just wrote a code in MATLAB to simulate the behavior of the answer and the result is a function SomeHow asymptotic to $m=\frac{3n}{5}$ enter image description here

MR_BD
  • 550
  • 5
  • 18