Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
@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
Any thoughts on the issue I mentioned? The condition doesn't seem to hold as stated. – EuYu Oct 4 '12 at 19:07
up vote 2 down vote accepted

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!

share|cite|improve this answer
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! – brainail Oct 5 '12 at 6:44
Looks like you got it! – EuYu Oct 5 '12 at 12:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.