Spanning graph of regular graph Show that there exists $d'$ such that for every $d > d'$, every $d$-regular graph contains a spanning subgraph with minimum degree $\ge 10$ and girth $\ge 10$.
Any idea how to approach this question?
 A: Short version: choose a random subset of the edges, each edge being chosen with probability $p = d^{-0.9}$. Then apply the local lemma.

Long version: there are eight kinds of bad events.


*

*Type $1$: a vertex ends up with fewer than $10$ edges.

*Type $k$, for $3 \le k \le 9$: a cycle of length $k$ ends up entirely chosen.


The average degree of a vertex is $pd = d^{0.1}$, so the probability that we see less than half that degree (which is $\ge 10$ for $d$ sufficiently large) is at most $\exp(-d^{0.1}/8)$ by a Chernoff-type bound. In particular, this is smaller than any polynomial function of $d$. That's type $1$ events. Type $k$ events have probability $p^k = d^{-0.9k}$, which is straightforward.
For the overlap between these, we need to count the number of cycles of length $j$ containing a given vertex. This is at most $d^{j-1}$: we pick $j-1$ of the edges of the cycle by extending it from one end in one of $d$ ways, and the last edge must be the edge that closes the cycle, if that edge happens to exist.
As a result, a type $1$ event is mutually independent of all but $d$ other type $1$ events, and all but $d^{j-1}$ type $j$ events for each $j>2$. A type $k$ event is mutually independent of all but at most $k$ type $1$ events, and all but $k d^{j-1}$ type $j$ events for each $j>2$.
So set $x_1 = 1/d^2$ and $x_k = 2 d^{-0.9k}$ for each $k>2$. We check that for sufficiently large $d$:
\begin{align}
 e^{-d^{0.1}/8} &\le \frac1{d^2} \cdot \left(1 - \frac1{d^2}\right)^d \cdot \prod_{j=3}^9 \left(1 - 2 d^{-0.9j}\right)^{d^{j-1}}, \\
 d^{-0.9k} &\le 2 d^{-0.9k} \cdot \left(1 - \frac1{d^2}\right)^j \cdot \prod_{j=3}^9 \left(1 - 2d^{-0.9j}\right)^{k d^{j-1}}.
\end{align}
This is straightforward by the Bernoulli's inequality: $(1-x)^r \ge 1-rx$ for $r\ge0$ and $x\le1$. In particular, $$\left(1 - 2 d^{-0.9j}\right)^{d^{j-1}} \ge 1 - 2d^{-0.9j} \cdot d^{j-1} = 1 - 2d^{0.1j-1} \ge 1 - 2d^{-0.1}$$ for $j\le 9$, which can be made arbitrarily close to $1$ by taking $d$ sufficiently large.
