A graph is an ordered pair where is a finite nonempty set of vertices and is a set of two-element subsets of called edges. By convention, we write to denote an edge . The degree of a vertex is the cardinality of the set . A graph is said to be bipartite if where and implies or . Time for a little theorem:
If is a graph that is not bipartite, then there exist such that is even.
Proof: If there do not exist such that is even, let
Then every edge in contains a vertex from and a vertex from . It follows that is a bipartition of , and hence that is bipartite.