- #1
mrtanaka
- 3
- 0
Homework Statement
Prove: G is bipartite iff every subgraph H has an independent set containing |V(H)|/2
Homework Equations
independent set = set of mutually nonadjacent vertices.
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.