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

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?

share|cite|improve this question
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:

A multi-component bipartite graph

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.

share|cite|improve this answer

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.