9780023606922, Chapter 2 5, Problem 20E

Prévia do material em texto

Chapter 2.5, Problem 20E Step-by-step solution Step 1 of 1 Bipartite Graphs Bipartite Graph: G=(V,E) is a graph, and if there exist two subsets V such that and every edge in E is an incident on one vertex in one vertex in then the graph G is called Bipartite. Consider the following graph: 1 2 3 4 5 6 7 8 9 10 From the definition, the above graph is bipartite as every edge is incident on one vertex in and one vertex in Hence the disjoint sets are and