# Past exam question: probabilistic method to prove a partition of a graph exists

The following is a question from a past paper:

Let $G$ be a graph with an even number of vertices. Show that the vertices of $G$ can be partitioned into two parts $A$ and $B$ of equal size such that the number of edges between $A$ and $B$ is strictly larger than $\frac{|E|}{2}$.

Hint: Consider a random partition of the vertices into two parts of the same size.

I think I have shown that such a partition exists if the statement were for the number of edges between $A$ and $B$ is at least $\frac{|E|}{2}$. I have done this using expectations but I am unsure of how to proceed, or if this was even the correct approach in the first place!

Solution so far:

Take the graph G=(V,E) and for each vertex, randomly select whether it will lie in A with independent probability $p=\frac{1}{2}$. For each edge $e_i$ $\in$ $E$, define the random variable $X_i$ s.t. $X_i=1$ if $e_i$ connects A and B and 0 otherwise. Then, $\mathbb{P}(X_i=1)=\frac{1}{2}$ and $\mathbb{E}(X_i)=\frac{1}{2}$

Then, using the linearity of expectation:

$\mathbb{E}(number\ of\ edges\ connecting\ A\ and\ B)=\frac{|E|}{2}$

Since the expected number of edges crossing the partition is $\frac{|E|}{2}$, there must be at least one choice of $A,B$ that has at least $\frac{|E|}{2}$ edges crossing.

Assume that all possible choices for $A,B$ have fewer than $\frac{|E|}{2}$ edges crossing the partition, then we get that:

$\mathbb{E}(number\ of\ edges\ connecting\ A\ and\ B)<\frac{|E|}{2}$

I am unsure how to proceed to get to the required strict inequality and would appreciate any hints on that, and also, if this is the wrong approach or there is something wrong with my work so far, a different answer would be appreciated as there are no mark schemes!

Your derivation is not correct, because if you randomly assign a vertex to one of $A$ and $B$, it is not guaranteed the $A$ and $B$ obtained are of equal size.
Suppose there are $2n$ vertices in the graph. There are totally $\binom{2n}{n}$ possible partitions, in which $A$ and $B$ are of equal size. We randomly sample one of such partitions.
Now consider an edge $e = (u, v)$ of $G$. There are two possibilities such that $e$ connects $A$ and $B$: $(1)$ $u \in A, v \in B\$; $(2)$ $u \in B, v \in A$. For either case, there are $\binom{2n - 2}{n-1}$ corresponding partitions.
Let $X_e$ be a random variable such that $X_e = 1$ if $e$ connects $A$ and $B$ and $= 0$ otherwise. We have $$\mathsf{E}(X_e) = \Pr(X_e = 1) = \frac{2\binom{2n-2}{n-1}}{\binom{2n}{n}} = \frac{n}{2n-1} > \frac{1}{2}$$ Therefore, the expected total # of edges connecting $A$ and $B$ is more than $\frac{|E|}{2}$.
• @mathcomp Your derivation looks good to me if the question does not require the sets to be of equal size and the bound is just greater than or equal to $|E| / 2$. – PSPACEhard Mar 12 '17 at 9:26