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.

Prove that every graph $G$ with minimum degree $2m$ will have a bipartite subgraph having minimum degree $m$.

I have tried this proof by first taking one vertex $v$ and consider it in set $D_0$. Then i am taking m of its neighbours (out of $2m$) to form a set $D_1$. My main intension is to partition all vertex in G into $D_i$ s and create two partitions with $i$s as even in one partiotion and $i$s as odd in another partition.

But i am having a difficulty in proving that no edge exists between two $D_i$ in different levels

share|improve this question
2  
What have you tried so far, and why hasn't it worked? Do you have any ideas about how you might start doing it? You're much less likely to get help with something if you just post a question that certainly appears like it came directly from your homework, instead of giving the problem and some attempted solutions. –  qaphla Aug 19 '13 at 18:53
    
I changed my question to show my thought process –  Neel Choudhury Aug 19 '13 at 19:07
    
You gotta use the fact that any vertex in $G$ has a degree at least $2m$, and you are only using the fact there is at least one vertex like that. –  gt6989b Aug 19 '13 at 19:31
    
Don't know for sure, but I would think about inducting on $|V|+|E|$, removing an edge and now the bipartition appears by the Inductive Hypothesis. You end up with not having ability to remove an edge without touching some vertex of degree $2m$. There are limited possibilities for the ends of that edge you removed, try to classify them. –  gt6989b Aug 19 '13 at 19:49

1 Answer 1

Hint:

  • Let $G_0$ be any maximal bipartite subgraph of $G$.
  • Let $v_i \in V$ be some vertex of the smallest degree in $G_i$.
  • If $\mathrm{deg}_{G_i}(v_i) \geq m$, then you are done (and the sequence stops), otherwise set $G_{i+1}$ to be the graph with $v_i$ moved to the other side (and appropriate edges added or removed so that $G_{i+1}$ is also a maximal bipartite subgraph of $G$).
  • Observe, that with each turn, the number of edges of $\{G_i\}_i$ strictly increases, but the only way the sequence could stop is when $\mathrm{deg}_{G_\text{end}}(u) \geq m$ for all $u \in V$.

I hope this helps $\ddot\smile$

share|improve this answer
    
Thats really cool..But how can we assure that the sequence of steps will end –  Neel Choudhury Aug 19 '13 at 21:19
    
@Neel I have typeset the reason in boldface font. –  dtldarek Aug 19 '13 at 21:24
    
ok i got it as min degree is $2m$ we will always find one such vertex for any $G_i$..thanks this was really a nice proof –  Neel Choudhury Aug 19 '13 at 21:25
    
@Neel Don't forget, that there is implicit assumption that $G$ is finite (and as such it has finitely many edges). –  dtldarek Aug 19 '13 at 21:27

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.