Probability of maximum degree in On random graphs I by Erdos

661 Views Asked by At

In The Maximum Degree of a Random Graph by RIORDAN et al., the authors commented that the study of the distribution of the maximum degree $d^{max}(G)$ of a random graph $G$ was started by Erdos and Renyi in On random graphs I.

I failed to identify the discussion in that paper by Erdos et al. It contains the proofs of four theorems none of them on $d^{max}(G)$.

The only relevant thing I can infer is from the first theorem.

enter image description here

So, $d^{max}(G) = n-1$ for a completely connected graph. In that sense the probability of being $d^{max}(G) = n-1$ should be same as the probability in the theorem above.

Was this what RIORDAN et al. was referring to?

PS. The only problem is that in a completely connected graph the number of edges is $\frac{n(n-1)}{2}$ but Erdos assumed the number of edges to be $[\frac{1}{2}n \log n + c n]$ where $c$ is a constant.