Exercise 21 (Chapter Review)

For each part below, say whether the statement is true or false. Explain why the true statements are true, and give counterexamples for the false statements.

1. Every bipartite graph is planar.

2. Every bipartite graph has chromatic number 2.

3. Every bipartite graph has an Euler path.

4. Every vertex of a bipartite graph has even degree.

5. A graph is bipartite if and only if the sum of the degrees of all the vertices is even.