# 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$.

-
I don't understand what $|A|\leq O(\frac{n\ln\delta}\delta)$ means, as $n$ and $\delta$ are fixed (so I don't understand in what this gives a constraint about the cardinality of $A$. –  Davide Giraudo Sep 27 '12 at 20:29
I think if $T \le c n^k$ for some $c >0$ we can write $T = O(n^k)$ or $T \le O(n^k)$. So it just asks us to prove the existence of some constant $c>0$ such that $|A| \le c \frac{n \ln \delta}{\delta}$. –  Shubhodip Mondal Sep 28 '12 at 3:44
This is exercise 4 in section 1.6 in Alon and Spencer's "The Probabilistic Method". –  Douglas S. Stones Sep 29 '12 at 6:34
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$ and $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.