Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
7  
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
1  
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
1  
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
show 4 more comments

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.