Challenge: Bipartite Graph Check

Apply graph traversal algorithms to check whether a graph is bipartite.

We'll cover the following

Bipartite graphs

In this exercise, we’ll take a look at a special kind of graph called bipartite graphs. An undirected graph GG is called bipartite if we can split its set of vertices up into two partitions (let’s call them the “left” and the “right” vertices), such that all edges connect a left vertex to a right vertex. In other words, there are no edges between two left vertices or between two right vertices.

The following illustration shows an example of a bipartite graph. The left vertices are marked in red and the right vertices are marked in blue.

Get hands-on with 1200+ tech skills courses.