# Probabilistic approach to prove a graph theory theorem

A theorem in graph theory is as the following,

Let $G=(V,E)$ be a finite graph where $V$ is the set of vertexes and $E$ is the set of edges. Then there exists a vertex subset $W$, i.e. $W \subset V$, such that the number of edges connecting $W$ and $W^C$ is at least $\frac{|E|}{2}$, where $W^C = V\backslash W$ and $|E|$ is the total number of edges in the graph $G$.

The question is to prove this theorem by a probabilistic approach.

My idea is as follows:
Let $|V|=n,|W|=m$, then the maximum number of possible edges between $W,W^C$ is $m\times(n-m)$. The maximum number of possible edges in graph $G$ is $C_n^2 = \frac{n!}{2!\times(n-2)!}$. We can treat the edges as if they were randomly scattered in the $C_n^2$ positions, and with probability $p=\frac{m\times(n-m)}{C_n^2}$ one edge would connect $W,W^C$.

Then it is like a Bernoulli trial of $|E|$ times with success probability $p=\frac{m\times(n-m)}{C_n^2}$, and the probability there are at least $\frac{|E|}{2}$ edges connecting $W,W^C$ is $\sum\limits_{k = \left\lceil {\frac{1}{2}|E|} \right\rceil }^{|E|} {C_{|E|}^k{p^k}{{(1 – p)}^{|E| – k}}}$. But this probability is for a particular $W$. We need to show with probability there exists one or more such $W$ satisfying the conditions of the above-mentioned theorem. I got stuck here. Anyone can help with this proof? Thank you!

#### Solutions Collecting From Web of "Probabilistic approach to prove a graph theory theorem"

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

By linearity of expectation: $$\mathbb{E}(\text{number of edges connecting W and W^C}) = \mathbb{E}(\sum X_i) = \sum E(X_i) = \sum \frac{1}{2} = \frac{|E|}{2}$$

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

You can see that the claim holds with certainty because if you assume that all possible choices for $W$ have fewer than $\frac{|E|}{2}$ edges crossing the cut, then we get the contradictory:

$$\mathbb{E}(\text{number of edges connecting W and W^C}) < \frac{|E|}{2}$$

ETA: To those who are still confused – here is a small explicit example:
Suppose $V = \{v_1, v_2\}$ and $E = \{(v_1,v_2)\}$.

We consider all possible choices for $W$, where vertices are independently placed in $W$ with probability $\frac{1}{2}$:

1. $W = \emptyset$. No edges cross the cut. This has probability $\mathbb{P}(v_1 \notin W \cap v_2 \notin W) = \frac{1}{2}\cdot \frac{1}{2} = \frac{1}{4}$.
2. $W = \{v_1\}$. One edge crosses the cut. This has probability $\mathbb{P}(v_1 \in W \cap v_2 \notin W) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$.
3. $W = \{v_2\}$. One edge crosses the cut. Again, this has probability $\mathbb{P}(v_1 \notin W \cap v_2 \in W) = \frac{1}{4}$.
4. $W = \{v_1,v_2\}$. No edge crosses the cut. Again, probability is $\frac{1}{4}$.

Then, $\mathbb{P}((v_1,v_2) \textrm{ crosses the cut}) = \frac{1}{2}$ and the expected number of crossing edges is $$0\cdot \frac{1}{4} + 1\cdot \frac{1}{4}+1\cdot \frac{1}{4}+0\cdot \frac{1}{4} = \frac{1}{2} = \frac{|E|}{2}$$

If all of the possibilities had fewer than $\frac{|E|}{2}$ edges crossing the cut, the expectation would have to be less than $\frac{|E|}{2}$. Therefore, there must be at least one choice for $W$ such that at least $\frac{|E|}{2}$ edges crosses the cut. In this case, one such choice is $W = \{v_1\}$.