Diameter bound for a fixed-density binomial random graph
ID: diameter-bound-for-a-fixed-density-binomial-random-graph
For fixed , the missing common-neighbour count in a binomial random graph has expectation tending to zero. The Markov inequality therefore shows that every pair has a common neighbour with probability tending to one. On that event every graph distance is at most two, so the graph is connected and its graph diameter is at most two.
New to topics? Read the docs here!