Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a fairly basic inquiry but i would sleep better at night if i saw a proof of it.

Q: i know that if i take a connected subgraph with at least 2 vertices of any simple bipartite graph G that it has to be bipartite.

how would one go about proving that this is the case for any simple graph G.

i think that if G had vertices of all degree 2 i could prove it easily but above that i am not sure.

share|cite|improve this question
up vote 3 down vote accepted

Hint: If $G$ is bipartite, then its vertices can be split $V=V_1 \cup V_2$ so that the edges are subset of $V_1 \times V_2$.

Let $H$ be any subgraph of $G$ and let $V' \subset V$ be its vertices. Then you can split the vertices of $V'$

$$V'= (V'\cap V_1) \cup (V' \cap V_2)$$

and it is easy to see that this yields $H$ bi-partite.

P.S. if you are familiar with the fact that bipartite means two colorable , if you color the vertices of $G$ with two colors, that is a good coloring for any subgraph...

share|cite|improve this answer

Your Answer


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.