A bipartite graph G is a simple graph whose vertex set can be partitioned into two

Chapter 10, Problem 37

(choose chapter or problem)

A bipartite graph G is a simple graph whose vertex set can be partitioned into two disjoint nonempty subsets \(V_{1}\) and \(V_{2}\) such that vertices in \(V_{1}\) may be connected to vertices in \(V_{2}\), but no vertices in \(V_{1}\) are connected to other vertices in \(V_{1}\) and no vertices in \(V_{2}\) are connected to other vertices in \(V_{2}\). 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 \(V_{1}=\left\{v_{1}, v_{3}, v_{5}\right\}\) and \(V_{2}=\left\{v_{2}, v_{4}, v_{6}\right\}\).

Text Transcription:

V_1

V_2

V_1={v_1, v_3, v_5}

V_2={v_2, v_4, v_6}