1
$\begingroup$

I want to show for a Combinatorial Optimization lecture that bipartite graphs doesn't have cycles of odd length.

I think the idea is to prove that a bipartite graph doesn't have cycles by recurrence.

let's suppose that $G$ is a bipartite graph of even length for SOMETHING set. Let's show that the FOLLOWING SOMETHING is also a bipartite graph of even length.

Yet, what is the something to use as far as length can't be used... ? I think it is the number of vertex. A bipartite graph is bipartite if and only if it is 2-colorable (Wikipedia) but I'm not sure I'm going in the good way... Can you help me proving that bipartite graphs doesn't have cycles of odd length ?

I know a that a proof exists in Asratian, Armen S.; Denley, Tristan M.J.; H\"aggkvist, Roland, Bipartite graphs and their applications, Cambridge Tracts in Mathematics. 131. Cambridge: Cambridge University Press. xi, 259 p. (1998). ZBL0914.05049.

$\endgroup$
1
$\begingroup$

$G$ is bipartite if and only if its vertices are 2-colorable. Then show that any cycle of odd length cannot be $2$-colorable.

$\endgroup$
0
$\begingroup$

This is actually easy. It turns out that the converse is also true, and that's a bit harder to prove.

You can prove first that an induced subgraph of a bipartite graph is bipartite. This is easy. Then you show that an odd cycle is not bipartite. This can be done using the $2$-colorable characterization, which is also easy. Thus a bipartite graph cannot have an odd cycle as an induced subgraph. Done.

$\endgroup$
0
$\begingroup$

a graph is Bipartite graph if and only if it 2-color-able because its consist of two subset that every two vertices from the same set don't have an edge between them and every vertex in one set is connected to at least one vertex from the other set.

Now odd cycle have to be 3-color-able and not 2. (you start with a triangle (3 vertex cycle) and prove it needs three colors and then prove by induction for 5,7 and so on).

a neat trick to use is to color one vertex white and every adjacent vertex with black color and so on, if you reach contradiction then its not Bipartite.

hope it answers your question

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.