# Partition in graph connecting itself and other half

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.

• My best guess is for each vertex of the graph, randomly and independently place it in set $A$ with probability $\ln \delta/\delta$, and otherwise place in set $B$. Then apply the Lovasz Local Lemma. However, I'm not really getting the details to work out easily -- perhaps there is a better method. – Tyler Seacrest Oct 20 '14 at 15:52

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.

• Consider when you have a bunch of $\delta$-cliques with one element from each assigned to $A$. Then we connect each element assigned to $B$ some nodes which is connected only to elements previously assigned to $B$. Quite frankly, we could put an arbitrary number of such new nodes into the graph, and this would cause $\frac{|A|}{n}$ to approach $1$ as you add nodes in this clearly worst-case scenario. However, if you choose each element in (1) and (3) to maximize the number of unassigned neighbors, this scenario can't occur. – Andrew Koche Oct 29 '14 at 16:55