Show that every graph $G$ has a bipartite subgraph with at least half of the edges of $G$

Solution 1:

[I know you said use induction, but here's a direct solution using mono variance / extremal principle. Feel free to ignore this.]

Take any sets $A, B$ where $ A \cup B = V$ and $A \cap B = \emptyset$. Consider any vertex $a \in A$. If $a$ has strictly more edges with vertices in $A$ than in $B$, then move it to $B$. This process will strictly increase the number of edges in $A \times B$, hence has to eventually stop.

Claim: The final set has at least $|E(G)| / 2$ edges in $A \times B$.

Let $deg_X (v)$ denote the degree of vertex $v$ to the set of vertices in $X$. Then, the number of edges in $A \times B$ is equal to $(\sum_a \deg_B a + \sum_b \deg_A b)/2$, and the total number of edges in the graph is equal to $\left[ \sum_a (\deg_A a + \deg_B a) + \sum_b (\deg_A b + \deg_B b) \right] /2$. The claim follows because $\deg_A (a) \leq \deg_B (a)$ for any vertex $a \in A$, and $\deg_B (b) \leq \deg_A (b)$ for any vertex $b \in B$.

Solution 2:

HINT: Let $P(n)$ be the statement that every graph on $n$ vertices has a bipartite subgraph with at least $|E(G)|/2$ edges. The induction step of your argument will be to show that $P(n)$ implies $P(n+1)$. Thus, you’ll assume $P(n)$ as your induction hypothesis, let $G$ be an arbitrary graph with $n+1$ vertices, and try to show that $G$ has a bipartite subgraph with at least $|E(G)|/2$ edges.

Pick a vertex $v$ of $G$, and let $H$ be the graph obtained from $G$ by deleting $v$ and all edges of $G$ incident at $v$. If $d=\deg(v)$, $|E(H)|=|E(G)|-d$. By the induction hypothesis $H$ has a bipartite subgraph $B$ with at least $|E(H)|/2$ edges; let $V_1$ and $V_2$ be the vertex sets of this subgraph. Without loss of generality we may assume that $V_1\cup V_2=V(H)$, i.e., that $B$ keeps all of the vertices of $H$. (Why?) For $i=1,2$ let $d_i$ be the number of edges between $v$ and $V_i$ in $G$. Choose $i\in\{1,2\}$ so that $d_i\ge\frac{d}2$.

Use the choice of $i$ to decide whether to add $v$ to $V_1$ or to $V_2$ and which of the $d$ edges of $G$ incident at $v$ to keep in order to extend $B$ to a bipartite subgraph of $G$ with at least $|E(G)|/2$ edges.

Solution 3:

Pick any vertex $v$.

Take a bipartite subgraph $H_1$ of $G - v$ which spans $V_{G} \setminus\{v\}$ and satisfies $\lvert E_{H_1} \rvert \ge \frac{1}{2} \lvert E_G \rvert$.

Let $H_1$ partition $V_G \setminus\{v\} = A \sqcup B$. Where $A$ has at least as many edges incident with $v$ as $B$ does. Add $v$ to $B$ and include all edges incident with $A$ to form your subgraph.