Discrete math Please write your answer neatly so that I can

Discrete math. Please write your answer neatly so that I can read it.

Prove that if each component of a graph is bipartite, then the entire graph is bipartite.

Solution

Let G1, . . . , Gn be the bipartite components of G.

Since a graph H is bipartite iff there are no odd cycles in H, there are no odd cycles in any Gi .

Since none of the Gi are connected with each other, composing them together does not create new cycles.

Thus, there are no odd cycles in G either, which means that G is bipartite.