there exists a bipartite graph whose size $\geq \frac{m}{2}$

Question

The question I am trying to solve now is "Prove that every graph $G$ has a bipartite subgraph of size $\geq \frac{m}{2}$" by using a probability method (defining a sample space and a random variable).

I wonder if my answer below is right, so I would appreciate it if you can check it.

1) Define a sample space $\Omega$ = {the set of all possible bipartite subgraphs $V_1 \bigsqcup V_2$ of $G$}.

2) Define a random variable $X: \Omega \rightarrow \mathbb{R}$ such that for $V_1 \bigsqcup V_2 \in \Omega$, $X(V_1 \bigsqcup V_2)$ is the number of edges of $V_1 \bigsqcup V_2$. Also, $X= \sum^m_{i=1}Y_i$ where $Y_i$ is the indicator of the existence of the edge $e_i$ in $V_1 \bigsqcup V_2$. By definition of $X$, $\forall V_1 \bigsqcup V_2 \in \Omega$, the maximum size of a bipartite subgraph $\geq X(V_1 \bigsqcup V_2)$.

3) The expected value $E(X) = \sum^m_{i=1} E(Y_i) = \sum^m_{i=1} P(e_i \in V_1 \bigsqcup V_2) = \sum^m_{i=1} \frac{1}{2} = \frac{m}{2}$. For every $i$, $P(e_i \in V_1 \bigsqcup V_2) = \frac{1}{2}$ because $e_i$ is either "in $V_1 \bigsqcup V_2$" or "not."

Thank you in advance!

Answer 1

I am having a tough time following your notation, OP. I am not positive if you meant it this way or not, but not every bipartite subgraph of $G$ is in the set $\Omega$ as you defined in 1).

This is how I would approach this problem: Partition randomly $V(G)$ into two sets $V_1$ and $V_2$ as follows. For each vertex $v$ flip a fair coin: Heads vertex $v$ goes into $V_1$; tails $v$ goes into $V_2$. Now from this partition of $V(G)$ into $V_1$ and $V_2$, we create a subgraph $G_B$ of $G$ that is necessarily bipartite, with parts $V_1$ and $V_2$. For each edge $uv \in E(G)$, the edge $uv$ is also in $G_B$ iff either $u$ is put into $V_1$ and $v$ into $V_2$, or $u$ is put into $V_2$ and $v$ into $V_1$.

Then for each $e \in E(G)$ the probability that the partitioning of $V(G)$ into $V_1$ and $V_2$ is such that edge $e$ is also in $G_B$ is precsisely $\frac{1}{2}$. Can you finish from here.

Answer 2

I don't think that your reasoning is valid. The fact that $e_i$ is either "in $V_1\cup V_2$" or "not" does not implies that the probability that the edge is in is one-half. Taking another (more simple) example, the edge $e_i$ is either connected to all other edgess, or "is not". But the probability that the edge is connected to all other edges is clearly not one-half.

If you were looking at $\Omega$ the set of all subgraph of $G$, then yes you would have $E(X)=1/2$ : in all subgraphs of $G$, there is an unique 1-to-1 correspondance between graphs including $e_i$ and not including $e_i$. But here, with $\Omega$ the set of all possible bipartite subgraphs, this is not the case for any graph $G$.

For instance lets define $G = K_3$ the complete graph on 3 labelled vertices. It has 7 bipartite subgprahs (3 with 2 edges, 3 with 1 edges and one with no edges). Then for every edge $P(e_i \in V_1\cup V_2)=3/7$.