Show that a graph is bipartite if, and only if, it does

Chapter 10, Problem 50E

(choose chapter or problem)

Problem 50E

Show that a graph is bipartite if, and only if, it does not have a circuit with an odd number of edges. (See exercise for the definition of bipartite graph.)

bipartite graph

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 (ii), you can see that G is bipartite with mutually disjoint vertex sets V1 = {v1, v3, v5} and V2 = {v2, v4, v6}.

(i)

(ii)

Find which of the following graphs are bipartite. Redraw the bipartite graphs so that their bipartite nature is evident

a.

b.

c.

d.

e.

f.