|
Use induction on $n$ to show that every graph on $n$ vertices has a bipartite subgraph with at least $|E(G)|/2$ edges. I tried some examples and see that it works. But I am not sure how to formulate the problem using n to use induction. Any tips or insights? |
|||||
|
|
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. |
|||
|
|
|
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. |
||||
|
|
|
[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$ then 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_A a + \sum deg_B 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$. |
|||
|
|
