Question on Sparse Random Graphs

Question

I saw stated in a paper the following result but without a reference or a proof.

Let $G$ be an Erdos-Renyi random graph with $n$ nodes and probability of connection $c/n$ with $c>1$. Let $H$ be its giant component (which exists and has $\alpha(c)n$ nodes almost surely where $\alpha$ is a well known function). Then the graph $H$ has paths with only one connection to the rest of the graph of length $O(\log n)$ asymptotically almost surely.

Can somebody show me why is this true or give me a reference? Thanks a lot!

Answer 1

Start with some/random vertex $v_1$. With probability $a_1=n p (1-p)^{n-1}\approx ce^{-c}$ it has exactly one neighbor, $v_2$. The probability that $v_2$ has exactly one additional neighbor, $v_3$, is $a_2=n p (1-p)^{n-2}$ which is also close to $ce^{-c}$. The probability that each subsequent vertex has exactly one new neighbor is again roughly $A=c e^{-c}$. This means that with probability roughly $A^k$ we see a path of length $k$ beginning at $v_1$. If $k=c_1 \log n$ for some small enough $c_1$ then this probability is $n^{-c_2}$ for some $c_2<1$.

After these $k$ steps there is a fixed probability (roughly $\alpha(c)$) that the last vertex $v_k$ is then connected to the giant component. So this means that the expected number of paths of logarithmic length connected to the giant component is large ($n^{1-c_2}$). We then use standard arguments (say, second moment) to show that with high probability there are such paths.

Answer 2

in the reference corner, check out:

• Rick Durrett's "Random Graph Dynamics" (2007), chapter 2, section 4
• Bela Bollobas' "Random Graphs" (2000), chapter 7, section 1

hope this helps