Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
this looks to be a duplicate of this question. One should be closed. –  robjohn Jan 29 '13 at 16:53

3 Answers 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.

share|improve this answer

[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$.

share|improve this answer
    
Nice. I take it $V$ is the vertex set of $G$. –  Gerry Myerson Jan 30 '13 at 3:29

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.