For a fixed graph \(H\)  with \(s\)  vertices and edges, it is known [1]} that the supercritical random graph \(G(m, \frac{1+\epsilon }{m})\)  contains an embedding of \(H\)  into \(G\)  as long as \(s= O(m/\log m)\) . Furthermore the width of the embedding is \(O(\log m)\) . The probability that two vertices in \(G\)  are connected is larger than \(\frac{1+\epsilon }{n/B}\) . Therefore we can embed \(H\)  into a subgraph \(H^{\prime }\)  of \(G\)  whose size is at most \( s\log n\)  such that \(H\)  is a minor of \(H^{\prime }\) . Furthermore as the vertices of \(G\)  are paths of length \(B\)  (in \(P_n\) ), the embedding of \(H\)  into \(G\)  directly translates to an embedding of \(H\)  into \(P^{\prime }\)  whose width is
\(O(B \log n)=O(\log n)\) . Choosing \(H\)  with \(s\)  vertices and edges and treewidth \(\Omega (s)\)  concludes the proof.
