9780023606922, Chapter 2, Problem 26E

Prévia do material em texto

Chapter 2, Problem 26E Step-by-step solution Step 1 of 1 Consider the following statement: A graph G is bipartite if and only if every closed path in G has even length. Consider a closed path in the graph G. Therefore, V1 = and since the graph G is a bipartite graph without loss of generality consider E A and since is adjacent to therefore it should belong to another set E B and since is adjacent to E A and so on. Therefore, belongs to A and even number of edges are there in the path till this vertex and belongs to B and odd number of edges are there in the path till this vertex. Since, Vn = V1 E A it implies that there should be even number of edges in the path to complete the cycle. Therefore, A graph G is bipartite if and only if every closed path in G has even length.