Graph with Cycle and Two-Colorable

Question

i think if the graph G has an odd cycle, it's not two-colorable, otherwise it can be two colorable.

i read in one notes that the following is True: we couldent two-colorable any graph G that has cycle.

anyone could clarify me ?

Answer 1

This is correct: if $G$ has an odd cycle, then $G$ is not two-colorable. Suppose that $V$ is the set of vertices of $G$, and $c:V\to\{0,1\}$ is a two-coloring of $V$ with the colors $0$ and $1$. Suppose further that $C=\{v_0,v_1,\ldots,v_n\}$ is a cycle in $G$. We can start the listing of vertices of $C$ at any point in the cycle, so we may assume that $c(v_0)=0$. Clearly this implies that $c(v_1)=1$, $c(v_2)=0$, and so on. It’s clear, in fact, that if $0\le k\le n$, then

$$c(v_k)=\begin{cases} 0,&\text{if }k\text{ is even}\\ 1,&\text{if }k\text{ is odd}\;. \end{cases}$$

And $v_n$ is adjacent to $v_0$, so we must have $c(v_n)=1$, which implies that $n$ is odd. Finally, $C$ has $n+1$ vertices (and edges), so $C$ must be an even cycle.

In short, if $G$ has a two-coloring, then every cycle in $G$ is even.

Answer 2

we couldnt two-colorable any graph G that has cycle. 

This is not true. The right statement is the following Theorem:

Theorem A graph $G$ is two colorable if and only if it has no odd cycle.

Here odd cycle means cycle of odd length.

Brian proved one implication. For the other implication, note that it is enough to prove the statement for each component, so you can assume that $G$ is connected.

Now you can 2-color the graph the following way: pick some vertex $v$ as the start vertex.

Color $v$ with color $0$, and color each vertex $u$ with color 0/1 if there exists a path of even/odd length from v to u. Then, the condition implies that each vertex is colored the right way (i.e. by ONE color, not both colors), and that this is a good 2 coloring.