Challenge: Bipartite Graph Check

Bipartite graphs

In this exercise, we’ll take a look at a special kind of graph called bipartite graphs. An undirected graph $G$ 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.