Graph can be partitioned into A and B with $|A| \le O(n\log \delta/\delta)$ Let $G = (V,E)$ be a graph with $n$ vertices and minimum degree $\delta > 10$. Prove
that there is a partition of $V$ into two disjoint subsets $A$ and $B$ so that $|A| \le O (\frac{n \ln \delta}{\delta})$ , and
each vertex of $B$ has at least one neighbor in $A$ and at least one neighbor in $B$.
 A: Because this is a textbook problem, I try to put my thoughts related to the text.
If we think about related problems, one can realize that $A$ is actually a dominating set:
  for every vertex in $B$, it has some neighbor in $A$.
  However, we require $B$ to have one more property: it contains no isolated vertices after $A$ is removed.
  Observe that, given a dominating set $D$ of $G$,
  if we move all the isolated vertices in $G|_{V-D}$ into $D$,
  then we have a dominating set with desired property satisfied.
This motivates a binomial sampling as follows: with a parameter $p \in (0,1)$,
  for each $v \in V$, $\Pr[v \in A_1] = p$.
  Let $A_2$ be the set of vertices not dominated by $A_1$
  (that is, for each vertex $w \in A_2$, none of its neighbors is in $A_1$).
  As described in the text, $A_1 \cup A_2$ is a dominating set.
Now let $A_3$ be the set of vertices not in $A_1 \cup A_2$,
  but all its neighbors are in $A_1$ or $A_2$. If we move $A_3$ into the dominating set,
  then as discussed above, $A = A_1 \cup A_2 \cup A_3$ satisfies the requirement.
  We compute the expectation of $|A|$, which is ${\bf E}[|A_1|] + {\bf E}[|A_2|] + {\bf E}[|A_3|]$.
  The only difficulty lies in $|A_3|$. Consider $v \in A_3$, and one of its neighbor $w$.
  Then $\Pr[w \in A_1] = p$ and $\Pr[w \in A_2] < (1-p)^{\delta+1}$.
  Thus $\Pr[(w \in A_1) \vee (w \in A_2)] < p + (1-p)^{\delta+1}$.
  Therefore $\Pr[v \in A_3] < (1-p)(p + (1-p)^{1+\delta})^\delta$.
Therefore the expected size of $A$ is
  \begin{align*}
    n \Big( \big( p + (1-p)^{1+\delta} \big) + (1-p)\big( p + (1-p)^{1+\delta}\big)^{\delta} \Big)
  \end{align*}
  If we plug in $p = \ln(1+\delta)/(1+\delta)$, note that $p + (1-p)^{1+\delta} < 1$,
  so this is $O(n\ln\delta/\delta)$ as desired.
A: Here is an approach that I think avoids assumptions of independence of neighbors sets (I bound by using an independent set of vertices). I think that otherwise making this assumption causes trouble: consider $K_{\delta, \delta}$. Using the notation of the above answer, for any vertex $v$ in the graph:
\begin{align*}
Pr[v \in A_3] = (1-p)p^{\delta} + (1-p)^{\delta}(1 - p^{\delta} - (1-p)^{\delta})
\end{align*}
which is bigger than $(1-p)(p+(1-p)^{1+\delta})^{\delta}$ for $\delta = 20$ and $p = 0.145 \approx \ln(1+20) / (1 + 20)$ (though the choice of $p$ is unimportant here), against the described bound.
I think if we randomly choose a first set $A_1$ then consider the set $\overline{A_2}$ of vertices not in $A_1$ and not adjacent to $A_1$, we can bound by taking a maximal independent subset $A_2$ of $\overline{A_2}$ and then proceeding as above. I am still a little suspicious of my approach, since I never really used the specific bound $\delta > 10$.

Construct a subset $R$ of the vertices $V$ by adding each vertex to $R$ independently with fixed probability $p$ (with $p$ to be determined later). Let $\overline{S}$ be the set of vertices $v$ which are not in $R$ and are not adjacent to any vertices in $R$.
Construct a set $S \subseteq \overline{S}$ as follows. If $\overline{S} = \varnothing$, then let $S = \varnothing$. Otherwise, order the vertices of $\overline{S}$ somehow: $\overline{S} = \{v_{1}, \ldots, v_{k}\}$. Add $v_{1}$ to $S$. For $i = 2, \ldots, k$, if $v_{i}$ is not adjacent to any vertices already in $S$, then add $v_{i}$ to $S$. Otherwise, discard it. (The point of this is to get a maximal independent subset.)
Every vertex $v \in V$ must either be in $R$, be in $S$, or be adjacent to a vertex in $R \cup S$: assume for contradiction that $v \not \in R \cup S$ and $v$ is not adjacent to any vertices in $R \cup S$. Since $v \not \in R$ and $v$ is not adjacent to any vertices in $R$, $v \in \overline{S}$. Since $v \not \in S$, it must have been discarded in the above procedure because it had a neighbor already in $S$, i.e. $v$ is adjacent to a vertex in $R \cup S$, a contradiction.
So $R \cup S$ is a dominating set. Let $T$ be the set of vertices $v \in V \setminus (R \cup S)$ such that all neighbors of $v$ are in $R \cup S$. Choose $A = R \cup S \cup T$ (so $B = V \setminus A$). Since $R \cup S$ is dominating, each vertex $b \in B$ is adjacent to a vertex in $A$. Furthermore, such $b$ must have a neighbor in $B \setminus \{b\}$ since otherwise $b \in T \subseteq A$. This choice of $A$ and $B$ then satisfies the problem.
$R,S,$ and $T$ are disjoint, so $\mathbb{E}[|R \cup S \cup T|]=\mathbb{E}[|R|] + \mathbb{E}[|S|] + \mathbb{E}[|T|]$. For any vertex $v \in V$, $\mathbb{P}[v \in R] = p$ so $\mathbb{E}[|R|] = np$. Since $S \subseteq \overline{S}$, $\mathbb{E}[S] \le \mathbb{E}[\overline{S}]$. $\mathbb{P}[v \in \overline{S}] \le (1-p)^{\delta + 1}$ so $\mathbb{E}[|S|] \le n(1-p)^{\delta + 1}$.
Given a vertex $v \in V$ with $d \ge \delta$ neighbors and non-empty $R' \subset N_G(\{v\})$ (strict subset), consider the event $E_{v, R'}$ that $v \not \in R \cup S$, $R' \subseteq R$, and $N_G(\{v\}) \setminus R' \subseteq S$. If any vertices in $N_G(\{v\}) \setminus R'$ are adjacent, then $Pr[E_{v,R'}] = 0$. Likewise, if any vertices in $R'$ are adjacent to any vertices in $N_G(\{v\}) \setminus R'$, then $Pr[E_{v,R'}] = 0$. This leaves the case when $R'$ and $N_G(\{v\}) \setminus R'$ have no common edges and $N_G(\{v\}) \setminus R'$ is an independent set. The probability that $N_G(\{v\}) \setminus R' \subseteq S$ is at most the probability that $N_G(\{v\}) \setminus R' \subseteq \overline{S}$ so:
\begin{align*}
Pr[E_{v,R'}] \le (1-p)p^{|R'|} (1-p)^{d-|R'|}(1-p)^{\delta-1}
\end{align*}
since $N_G(\{v\}) \setminus R'$ has at least $\delta - 1$ neighbors other than $v$, none of which can be in $R'$. It is clear that this bound then also works in the two "$0$-cases" above. Then:
\begin{align*}
    \mathbb{P}[v \in T] &\le (1-p)\left[p^{d} + \sum_{r=1}^{d-1} \binom{d}{r}p^{d-r}(1-p)^r(1-p)^{\delta-1}\right] \\
    &= (1-p)[p^{d} + (1-p)^{\delta-1}(1 - p^{d} - (1-p)^{d})] \\
    &\le (1-p)[p^{d} + (1-p)^{\delta-1}] \\
    &\le (1-p)p^{\delta} + (1-p)^{\delta}\\
    \Longrightarrow \mathbb{E}[|R|+|S|+|T|] &\le np + n(1-p)^{\delta+1} + n(1-p)p^{\delta} + n(1-p)^{\delta} \\
    &\le 2np + 2n(1-p)^{\delta} \\
    &\le 2np + 2ne^{-p\delta}
\end{align*}
From taking the derivative, $p = \ln \delta / \delta$ is the best choice, giving $\mathbb{E}[|R \cup S \cup T|] \in O(\frac{n \log \delta}{\delta})$, so it exists.
