A bipartite graph G = (V, E) is a graph whose vertex set V can be partitioned into two disjoint sets X and Y such that every edge in E has one endpoint in X and the other in Y. Informally, a graph is bipartite if we can color its vertices red or black such that each edge connects a red vertex to a black vertex.

If G is bipartite, then it cannot contain any odd-length cycles. In fact, the converse is also true. If a graph G does not contain any odd-length cycles, then it is bipartite. Thus, odd cycles are the only obstacle to bipartiteness.

We can determine whether a graph is bipartite in linear time by doing a single BFS or DFS traversal. The pseudocode below checks bipartiteness with BFS.

Take a look at C++ implementation.

Try your hand at problem BUGLIFE which uses this idea.

**Reference:** Algorithm Design by Kleinberg and Tardos

28.635308
77.224960

### Like this:

Like Loading...

*Related*