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

$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!

-
 That doesn't seem right. Every complete graph is biconnected but has a maximally independent subset of a single vertex. – EuYu Oct 4 '12 at 17:50 If this is homework, you can add the homework tag. – Graphth Oct 4 '12 at 18:47 @Graphth I corrected the question. – jofisher Oct 4 '12 at 19:01 @jofisher Great, it's just a way to let people know it is your homework, so hopefully they'll just give you little hints instead of doing the entire problem for you. – Graphth Oct 4 '12 at 19:03 @EuYu In this case yes, this is homework, but in other case it was just my interest, which appeared after homework. Sorry. – jofisher Oct 4 '12 at 19:03
show 3 more comments

## 1 Answer

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!

-
 In the forward direction it is obviosly for me (skip 1-4 question). In the backward direction: 1. No (because for odd cycle of size |V| = N: a(H) = (N - 1)/2, but |H| / 2 = (N - 1) / 2 + 1 / 2) 2. (N - 1) / 2 3. Yep, if a graph without odd cycle, that it is bipartite (A graph is bipartite if and only if it does not contain an odd cycle). I think this is the proof! – jofisher Oct 5 '12 at 6:44 Looks like you got it! – EuYu Oct 5 '12 at 12:23