# bipartite graph, no odd cycles, one question about the proof

I found a proof of the fact that if a graph G is bipartite(1), then it cannot have any odd cycles(2). I have a question about $(2) \Rightarrow (1)$. Why is it sufficient to assume that G is connected?

-
Because if $G$ isn’t connected, you can work in each component separately. –  Brian M. Scott Jan 7 '13 at 18:50
Right, indeed. Thanks a lot. –  Bilbo Jan 7 '13 at 18:59
You’re welcome. –  Brian M. Scott Jan 7 '13 at 19:00
I’m no graph theorist, but I wouldn’t have called that a product: you’re just concatenating two paths in a single graph. –  Brian M. Scott Jan 7 '13 at 20:51
Yes, concatenation is very often denoted by simple juxtaposition, as in $PQ^{-1}$, and yes, on the rare occasions when I’ve dealt with graph products, they’ve been explicitly indicated by some symbol. –  Brian M. Scott Jan 7 '13 at 21:10

It's a consequence of the following:

A graph is bipartite if and only if each of its components are bipartite.

So, for example, this graph is bipartite, since each of its components are bipartite:

This generalises to:

A graph is $k$-colourable if and only if each of its components are $k$-colourable.

This generalises to:

The chromatic polynomial of a graph is the product of the chromatic polynomials of its components.

This generalises to:

The Tutte polynomial of a graph is the product of the Tutte polynomials of its components.

-