3
$\begingroup$

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

  • 0
    @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.2012-10-04
  • 0
    Any thoughts on the issue I mentioned? The condition doesn't seem to hold as stated.2012-10-04

1 Answers 1

3

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!

  • 0
    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!2012-10-05
  • 0
    Looks like you got it!2012-10-05