Bipartition: Detecting Odd Length Cycles in Graphs

A bipartite graph is a graph whose vertices can be divided into two disjoint sets A and B such that every edge of the graph connects a vertex in set A to a vertex in set B, no edge connects the vertices of the same set. Let’s see how we can perform the Bipartition of a graph.

1. Chose any vertex of the graph as starting vertex and assign it to any set A or B(say A).
2. Now, all the neighbors of the starting node should belong to set B. Because, every edge connects the vertices of different sets.
3. Similarly, moving in a Breadth First manner, the neighbors of the nodes which were assigned to set B in step 2 should belong to set A.
4. After all the connected vertices have been traversed, we are left with three groups of vertices, vertices belonging to set A, vertices belonging to set B and disconnected vertices.
5. Any set can be assigned to any of the disconnected vertex as it won’t affect the property that every edge of the graph connects two vertices of different sets.
6. Now, the two sets A and B represent the bipartition of the graph.

If the two sets represent two colors, a Bipartite Graph will look like this:

Note that every edge connects two vertices of two different colors.

Now, what is the relation between bipartition and odd length cycles?
Bipartite graphs do not contain odd length cycles, or graphs with odd length cycles are not bipartite. Let us see why.

An odd length cycle, part of a bigger graph.

Suppose that while performing the bipartition of the graph, vertex 1 is assigned set A. It means that vertices 2 and 3 should be assigned set 2. But the vertices 2 and 3 are connected and hence cannot be assigned the same set. No matter what vertex among the three you start with, it is impossible to obtain the bipartition of such a graph.

Another non-bipartite graph, notice the presence of odd length cycle

Thus, we conclude that bipartite graphs do not contain odd length cycles.

But is the converse also true? Do all non-bipartite graphs contain odd length cycles? YES. Here is the proof.

In any bipartite graph, all the nodes at odd distances from the starting vertex belong to the same set (say set A). And, all the nodes at even distances from the starting vertex also belong to the same set (say set B).

If a graph is surely non-bipartite, there must be at least one edge connecting two nodes either both of set A, or both of set B. Which means there must be at least one edge connecting either two vertices of odd distance from starting vertex, or two vertices of even distance from starting vertex.

Let us say that one edge connects two vertices each having an even distance form starting vertex. Then, the length of the cycle including the starting vertex and the two vertices will be, Even + Even + 1 = odd. Thus we have an odd length cycle. A similar proof can be constructed using two vertices, each having an odd distance from starting vertex. Thus,

Every non-bipartite graph contains at least one odd length cycle.

Hence,

If a graph is bipartite it doesn’t contains any odd length cycles, but, if a graph is non-bipartite it surely contains at least one odd length cycle.