Bipartite graphs are both useful and common. For example, every path, every tree, and
every evenlength cycle is bipartite. In turns out, in fact, that every graph not containing
an odd cycle is bipartite and vice verse.
Theorem 2. A graph is bipartite if and only if it contains no odd cycle.