(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

Prove: G is bipartite iff every subgraph H has an independent set containing |V(H)|/2

2. Relevant equations

independent set = set of mutually nonadjacent vertices.

3. The attempt at a solution

I am trying to understand a solution given by my prof (for the backwards direction). As I understand it, he proved the contrapositive: suppose G is not bipartite and show that there exists a subgraph that does not have an independent with |V(H)|/2.

As G is not bipartite, we can find a cycle of odd length, {v_1, ...,v_2k+1}. He said if you take out k+1 vertices from this set, then by the pigeonhole principle, two of them will be consecutive (=> therefore adjacent). Therefore k+1 vertices cannot be independent.

I do not understand the step where k+1 vertices are removed, then somehow by the pigeonhole principle you conclude they are adjacent. I'd appreciate any help with this.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Graph Theory: Bipartite Graph Question

**Physics Forums | Science Articles, Homework Help, Discussion**