$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!
$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!
Since this is homework, I will not give a full solution but rather a series of hints.
The forward direction is rather simple:
For the backward direction:
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!