A Bipartite graph is a graph for which it is possible to divide the vertices into two disjoint sets such that there are no edges between any two vertices in the same set.