9780023606922, Chapter 2 5, Problem 24E

Prévia do material em texto

Chapter 2.5, Problem 24E Step-by-step solution Step 1 of 2 Determination of the graph (bipartite or not). Supposed graph is: 1 2 e₁ e₂ e₃ e₄ e₅ 3 e₆ 4 e₇ 5 It is not a bipartite graph. From the definition, a bipartite graph is one where there exist subsets V1 and V2 of V such that and every edge is incident on one vertex in V1 and one vertex in Hence from observation it is not possible to construct subsets which satisfy these conditions. Step 2 of 2 Hence, the above graph not bipartite.