Graph Theory: Bipartite Graph Question

[mrtanaka]

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.

 

[Robert1986]

Not all of the k+1 verticies are adjacent. He is saying that in the cycle, there are 2k+1 verticies, each one being connected to the next one. But, if you take out k+1, then at least two of them will be adjacent. Now, why is this true? Well, let's try to take as many verticies out of this cycle such that no two are adjacent. How would you do this, and how many can you do for a cycle of length 2k+1?

Do you see it? Post back if not.

 

[mrtanaka]

Thank you for replying. I see that if you take out k+1, at least two of them will be adjacent. but i do not see how this says anything about the size of the independent set, so i am still unclear