Question: Show that a graph is bipartite if, and only if, it does not have a circuit with an odd number of edges.

Exercise: A bipartite graph G is a simple graph whose vertex set can be partitioned into two disjoint nonempty subsets V1 and V2 such that vertices in V1 may be connected to vertices in V2, but no vertices in V1 are connected to other vertices in V1 and no vertices in V2 are connected to other vertices in V2. For example, the graph G illustrated in

(i) can be redrawn as shown in

(ii) From the drawing in

(iii) you can see that G is bipartite with mutually disjoint vertex sets V1 = {} and V2 = {}.