A

bipartite graph is a graph (in the

graph theory sense) where the vertices can be divided into two sets A and B, where every

vertex in A does not have an edge to any other vertex in A, and any vertex in B does not have an edge to any other vertex in B.

Bipartite graphs are used to solve a number of matching problems, such as maximizing matches of jobs to workers, and classes to classrooms.