$G$ is bipartite $\Leftrightarrow$ $\forall H$, $H$ is sub-graph of $G$ $\Rightarrow$ $\alpha(H) \ge \frac{|H|}{2}$

Question

$G$ is bipartite $\Leftrightarrow$ $\forall H$, $H$ is sub-graph of $G$ $\Rightarrow$ $\alpha(H) \ge \frac{|H|}{2}$, where $\alpha(H)$ is the vertex independence number of $H$

Give some clue please!

Thanks anyway!

Answer 1

Since this is homework, I will not give a full solution but rather a series of hints.

The forward direction is rather simple:

1. If the graph is bipartite then there is a bipartition of the vertices.
2. What can you say about the vertices of each bipartition?
3. How large is the largest bipartition?
4. Is each subgraph bipartite?

For the backward direction:

1. If a graph satisfies $$\alpha(H) \ge \frac{|H|}{2},\ \forall H\subseteq G$$ then can it have odd cycles?
2. What is the size of a maximally independent vertex set in an odd cycle?
3. Is a graph without odd cycles necessarily bipartite?

I will offer additional hints if you need them, but only if you make a serious effort and show me some of the progress you've made. Good luck!