In ["The mixing time of the giant component of a random graph"](http://arxiv.org/abs/math/0610459) by the aforementioned authors, in the last proof on page 19 it says something along the lines of


"It is well known and easy to verify that, since $m=O(n)$
, asymptotically almost surely the maximum degree occurring in $\mathcal{C}\_3(n,m)$ is $o(n^{0.02})$"


where $\mathcal{C}(n,m)$
denotes a random graph with $n$ vertices, $m$ edges, uniformly sampled among such graphs, and $\mathcal{C}\_3(n,m)$ denotes the variable conditioned on minimum degree 3 (which shouldn't influence the above statement).


I am wondering where the $n^{0.02}$
comes from, and how this is "well known". Can someone provide an original source for this statement or this kind of statement?



Question on a paper by Benjamini/Kozma/Wormald about a “well known fact”
I have no idea where the figure $n^{0.02}$ comes from. I would usually say it's well known that the maximum degree is $O(\log n)$ (actually even this is an overestimate). It's for example found in an Erd\H{o}s-R\'enyi paper with a title about random matrices, I think; or surely in any of the 'Random Graphs' books.


In any case, it is very easy to prove. One (lazy) way is: generate $G(n,p)$ with $p=1000(\log n)/n$. Standard applications of the Chernoff bound give you that a.a.s. this has all vertex degrees between $500\log n$ and $1500\log n$. Take a uniform random subgraph of this with $m$ edges and minimum degree three. Over both levels of randomness this is uniformly distributed, so it's $C\_3(n,m)$: done.


