Show that a graph is bipartite if and only if it does not have a cycle of odd length

In this article, we will prove that a graph is bipartite if and only if it does not have a cycle of odd length.

Proof Bipartite Graph does not contain an odd cycle

We will prove this by contradiction.

Suppose a Bipartite Graph G(V, E). Let V1 and V2 be the bipartitions of G. Assume graph G contains an odd cycle of length N.

odd cycle of length N

Since the graph is bipartite. We must be able to divide the vertices of the odd length cycle in set V1, V2 such that no adjacent vertices belong to the same set.

bipartite graph do not contain odd cycle

As we can see in the figure, we assigned set V1 and V2 to the vertices of the odd cycle alternately. The odd number vertex goes to set V1 and even number vertex goes to set V2.

But here is the problem. Both 1 and N are odd. Therefore, 1 and N belong to the same set. But this is not possible because adjacent vertices cannot belong to the same set.


Also, 1 and N are adjacent to a vertex belonging to set V2 so we cannot shift one of them to set V2.

This shows that if a graph contains an odd length cycle, it cannot be bipartite since we cannot partition the vertices of the odd cycle in set V1 and V2 such that no adjacent vertex belong to the same set.

Therefore, our assumption that the bipartite graph G contains an odd cycle is incorrect. Hence, we can say that a graph is bipartite if and only if it does not have a cycle of odd length.

Read
Prove Hypercube is Bipartite
Prove Petersen Graph is Non-planer

References
Graph is Bipartite iff No Odd Cycles

Leave a Comment

Your email address will not be published. Required fields are marked *