Proof. Let $P$ be $v_1,v_2,\dots ,v_l$. Let $x\in X(P)$ and let $y\in V(P)$ and $xy\in G$. We show $y\in \overline{X}(P)$.

Let $P_x$ be a path $P_x\sim P$ with endpoint $x$. Let $y=v_i$.

Case 1: $v_{i-1}{v}_i$ and $v_i{v}_{i+1}\in P_x$. We rotate through the edge $xy$ from $P_x$ to form a path $Q$. Of course $\overline{P}\sim Q$. Note in this path $Q$, either $v_{i-1}$ or $v_{i+1}\in X(P)$. This means $v_i\in \overline{X}(P)$.

Case 2: If either $v_{i-1}{v}_i$ or $v_i{v}_{i+1}\notin P_x$ then there was a first path $P^{\prime }$, when we were rotating from $P$ to $P_x$, where we removed one of $v_{i-1}{v}_i$ or $v_i{v}_{i+1}$.

Note carefully that this means that in $P^{\prime }$, one of $v_{i-1},v_i,v_{i+1}$ is an end of $P$. So $v_i\in \overline{X}(P)$. □

Proof. If $P$ is a longest path in $G$, we have that

$$e(X(P),V(G)\setminus P)=0,$$

otherwise we could rotate and extend $P$, contradicting maximality of $P$. By Lemma 11.2,

$$e(X(P),V(P)\setminus \overline{X}(P))=0.$$

So

$$e(X(P),V(G)\setminus \overline{X(P)})=0.$$

Note

$$|\overline{X}(P)|\le 3|X(P)|$$

so use expander condition to see

$$|X(P)|>\frac{n}{6}.\square$$

Proof.

$$\begin{array}{llll}\hfill \mathbb{P}(G\text{ not an expander})& \le \sum _{\begin{array}{c}A\subset [n]\\ |A|\le \frac{n}{6}\end{array}}\sum _{\begin{array}{c}B\subset [n]\\ |B|=n-3|A|\end{array}}\mathbb{P}(e(A,B)=0)& \hfill & \\ \hfill & \le \sum _{k=1}^{\frac{n}{6}}\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{n-k}{n-3k}\right){(1-p)}^{k(n-3k)}& \hfill & \\ \hfill & \le \sum _{k=1}^{\frac{n}{6}}\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{n}{2k}\right)e^{-pk(n-3k)}& \hfill & \\ \hfill & \le \sum _{k=1}^{\frac{n}{6}}{\left(\frac{en}{k}\right)}^{3k}{e}^{-pk(n-3k)}& \hfill & \\ \hfill & \le \sum _{k=1}^{\frac{n}{6}}{\left(\frac{e{n}^3}{k}{e}^{-p(n-3k)}\right)}^k& \hfill & \\ \hfill & \le \sum _{k=1}^{\frac{n}{6}}{\left(\frac{e{n}^3}{k}{n}^{-6}\right)}^k& \hfill & \\ \hfill & \le n^{-3}\square & \hfill & \end{array}$$

Proof. Let $E_i$ be the event that $G-v_i$ is an expander.

Let

$$M_i=\text{“the longest path in }G\text{ has the same length as the longest path in }G-v_i\text{”}.$$

Then

$$\begin{array}{llll}\hfill \mathbb{P}(G⁄\supset P_n)& \le \mathbb{P}\left(\bigcup _{i=1}^n{M}_i\right)& \hfill & \\ \hfill & \le n\mathbb{P}(M_1)& \hfill & \\ \hfill & \le n\mathbb{P}(M_1\cap E_1)+O(n^{-1})& \hfill & \\ \hfill & \le n\cdot \underset{G-v\in M_1\cap E_1}{\max }{\mathbb{P}}_{N(v_1)}(M_1)+O(n^{-1})& \hfill & \\ \hfill & \le n{(1-p)}^{\frac{n}{6}}+O(n^{-1})& \hfill & \end{array}$$ Since a longest path $P$ in $G-v_1$ has $|X(P)|\ge \frac{n}{6}$. So if $M_1$ is to hold, we cannot include any edges between $v_1$ and $X(P)$. To finish,

$$n{e}^{-\frac{pn}{6}}+O(n^{-1})=O(n^{-1}).\square$$

Proof of $G(n,p)\supset C_n$ when $p>\frac{20\log n}{n}$. Let $G_1\sim G(n,p_1)$ where $p_1=\frac{12\log n}{n}$, $G_2\sim G(n,p_2)$ where . Let $G=G_1\cup G_2$: then $G\sim G(n,p)$ where $p=(12+o(1))\frac{\log n}{n}$.

Define $E$ to be the event that $G_1$ is an expander. Define $P$ to be the event that $G_1\supset P_n$. Then

$$\begin{array}{llll}\hfill \mathbb{P}(G⁄\supset C_n)& \le \mathbb{P}(G⁄\supset C_n\cap E\cap P)+\underset{o(1)}{\underbrace{\mathbb{P}(E^c)+\mathbb{P}(P^c)}}& \hfill & \\ \hfill & \le \underset{G_1\in E\cap P}{\max }{\mathbb{P}}_{G_2}(G⁄\supset C_n)+o(1)& \hfill & \end{array}$$

Let $P$ be a Hamiltonian path in $G_1$.

Since $G_1$ is an expander, we have $|X(P)|>\frac{n}{6}$. So there are $\ge \frac{n}{6}$ edges that, if included, will complete a Hamiltonian cycle by Pósa rotation lemma. So

$$\mathbb{P}(G⁄\supset C_n)\le {(1-p)}^{\frac{n}{6}}+o(1)\to 0.\square$$