The following are equivalent formulations of the definition of a bipartite graph:
The proofs of the equivalences are (as per mathematical custom) left as an exercise for the inclined reader.
- The vertices of the graph may be partitioned into two sets A and B, with all edges of the graph go from a vertex in A to a vertex in B. (This is flyingroc's definition above, and is the most common).
- The graph has chromatic number 2.
- All cycles (loops) in the graph have an even length.