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.