Partition in graph connecting itself and other half

Question

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|\leq O(\dfrac{n\ln\delta}{\delta})$, and each vertex of $B$ has $\geq 1$ neighbor in $A$ and $\geq 1$ neighbor in $B$.

[Source: The probabilistic method, Alon and Spencer]

I would like to set up a probabilistic argument here, but not sure how to start.

Answer 1

I propose this algorithm for the partition:

1. Select an unassigned vertex and put it in $A$.
2. Put all the unassigned neighbors of vertices in $A$ in $B$.
3. Put all the unassigned neighbors of vertices in $B$ in $A$.
4. Repeat steps 2 and 3 until no more progress is made. If graph is partitioned, you're done. If not (in case of multiple components), return to 1.

This may not be a probabilistic argument, but at least it's an argument!

Edit: Oops, I completely missed $|A| \leq O(\frac{n \ln \delta}{\delta})$. Perhaps this would work:

1. Select an unassigned vertex and put it in $A$.
2. Put all the unassigned neighbors of vertices in $A$ in $B$.
3. Select an unassigned vertex without any neighbors in $B$ and put it in $A$.
4. Repeat steps 2 and 3 until no more progress is made. If graph is partitioned, you're done. If not, repeat steps 1 and 2 until graph is partitioned.

This will put at least $\delta$ times as many vertices into $B$ as $A$ at first, but then will taper off. I'm not sure how to ensure that $|A| \leq O(\frac{n \ln \delta}{\delta})$, but this is a possible starting point.