In a bipartite graph, the vertices can be divided into two sets such that:
All edges connect a vertex in one set to a vertex in the other
All edges stay within the same set
Every vertex has the same degree
There are no cycles