# 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!

• It's often easier to think about the expected number of edges across a random cut instead of the specific probabilities. Can you show that the expected number of edges connecting $W$ and $W^C$ is $\frac{|E|}{2}$? – Michael Biro Oct 21 '15 at 17:06
• @MichaelBiro Thank you for the suggestion. I kind of got it. So for any $W$ of size $m$, the expectation of number of edges bridging $W$ and $W^C$ is simply $p|E|$ where $p=\frac{m\times(n-m)}{C_n^2}=\frac{2m(n-m)}{n(n-1)}$. We only need to show $p\ge \frac{1}{2}$ for some $m=1,2,...,n-1$, which is now a trivial problem, right? – Sherry Oct 21 '15 at 18:04
• @MichaelBiro The response from my professor is that using expectation might not be rigorous. The objective is to show with probability 1 there exists $W$ st. there are at least half of the edges laying between $W$ and $W^C$ (and the expectation approach I show in the previous comment does support a guess that such $W$ should be of size $|V|/2$). However, the expectation of number of edges exceeding $|E|/2$ only implies with positive probability that there exists such $W$. Can you help think again about the problem? Thank you! – Sherry Oct 23 '15 at 1:57
• If there is a positive probability of selecting a $W$ with that property, then there must exist a $W$ with that property. This is the heart of the probabilistic method - it uses probability to prove something with certainty. – Michael Biro Oct 23 '15 at 2:01
• @MichaelBiro From my understanding, the graph is finite, so with positive probability that there are at least half edges are placed between $W$ and $W^C$ does not guarantee this event happens based on my "random edge placing". So probably my way of modeling the problem is not correct. – Sherry Oct 23 '15 at 2:09

## 1 Answer

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\}$.

• How do you get $P(X_i=1)=1/2$? – Tony Oct 23 '15 at 3:33
• Thanks for you reply. I still have trouble understanding your solution. For example, given random variables $X_i, i=1,2,...,n$ st. $(X_1+X_2+...+X_n)/n > a$, then I can surely see one of the X_i must take a value larger than $a$ no matter what the realization is. However, I don't understand why one of $X_i$ must be larger than $a$ provided $\Bbb{E}X_i>a$, or $\Bbb{E}((X_1+X_2+...+X_n)/n) > a$. Could you help add more details in your answer? – Sherry Oct 23 '15 at 5:24
• @Tony If edge $e_i = (a,b)$ then $\mathbb{P}(X_i = 1) = \mathbb{P}((a \in W \cap b \in W^C) \cup (a \in W^C \cap b \in W)) = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{2}$. – Michael Biro Oct 23 '15 at 11:28
• @Sherry If every cut has fewer than $\frac{|E|}{2}$ edges crossing it then $\mathbb{E}(\textrm{number of edges connecting$W$and$W^c$}) =\sum_{i = 0}^{|E|} i \cdot \mathbb{P}(\textrm{$i$edges connect$W$and$W^C$}) < \sum_{i = 0}^{|E|} \frac{|E|}{2} \cdot \mathbb{P}(\textrm{$i$edges connect$W$and$W^C$})= \frac{|E|}{2} \sum_{i = 0}^{|E|} \cdot \mathbb{P}(\textrm{$i$edges connect$W$and$W^C$}) = \frac{|E|}{2}$. This directly contradicts the calculation that the expectation is $\frac{|E|}{2}$. This means that at least one $W$ must be crossed by at least $\frac{|E|}{2}$ edges. – Michael Biro Oct 23 '15 at 11:34
• @MichaelBiro The probability seems not trivially $1/2$ for every $X_i$ because edges cannot overlap. I assume you let $|W|=|V|/2$? Every time one edge $e$ connects $W$ and $W^C$, then all forthcoming edges cannot overlap $e$. – Tony Oct 23 '15 at 15:36