Try It Now

Work these exercises to see how well you understand this material.

Exercises

  1. Apply Theorem 9.6.12 to prove that once n gets to a certain size, a Kn is nonplanar. What is the largest complete planar graph?

  2. What are the chromatic numbers of the following graphs?

     

  3. What is χ(Kn), n ≥ 1?

  4. Complete the proof of Euler's Formula.

  5. Let G = (V, E) with |V| ≥ 11, and let U be the set of all undirected edges between distinct vertices in V . Prove that either G or G′ = (V, Ec) is nonplanar.

  6. Prove that a bipartite graph with an odd number of vertices greater than or equal to 3 has no Hamiltonian circuit.

  7. Suppose you had to color the edges of an undirected graph so that for each vertex, the edges that it is connected to have different colors. How can this problem be transformed into a vertex coloring problem?

 

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.