Print bookPrint book

Try It Now

Site: Saylor Academy
Course: CS202: Discrete Structures
Book: Try It Now
Printed by: Guest user
Date: Friday, February 4, 2022, 5:49 PM

Description

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

Table of contents

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.

Solutions

  1. Answer: Theorem 9.6.12 can be applied to infer that if n ⩾ 5, then Kn is nonplanar. A K4 is the largest complete planar graph.

  2. Answer:
    1. 4
    2. 3
    3. 3
    4. 3
    5. 2
    6. 4

  3. Answer: The chromatic number is n since every vertex is connected to every other vertex.

  4. Answer: Suppose that G′ is not connected. Then G′ is made up of 2 components that are planar graphs with less than k edges, G1 and G2. For i= 1,2 let vi, ri, and ei be the number of vertices, regions and edges in Gi. By the induction hypothesis, vi+ ri − ei= 2 for i = 1,2.

    One of the regions, the infinite one, is common to both graphs. Therefore, when we add edge e back to the graph, we have r = r1 + r2− 1, v = v1 + v2, and e = e1 + e2 + 1.

    \begin{align*} v+r-e &= (v_1 + v_2) + (r_1 + r_2 - 1) - (e_1 + e_2 + 1) \\ &= (v_1 + r_1 - e_1) + (v_2 + r_2 - e_2) - 2 \\ &= 2+2-2 \\ &= 2 \end{align*}

  5. Answer: Since |E| + E^c = \frac{n(n-1)}{2}, either E or Ec has at least \frac{n(n-1)}{4} elements. Assume that it is E that is larger. Since \frac{n(n-1)}{4} is greater than 3n − 6 for n ⩾ 11, G would be nonplanar. Of course, if Ec is larger, then G′ would be nonplanar by the same reasoning. Can you find a graph with ten vertices such that it is planar and its complement is also planar?

  6. Answer: Suppose that ( V, E) is bipartite (with colors red and blue), |E|is odd, and (v1, v2, . . . , v2n + 1, v1) is a Hamiltonian circuit. If v1 is red, then v2n + 1 would also be red. But then {v2n + 1, v1} would not be in E, a contradiction.

  7. Answer: Draw a graph with one vertex for each edge, If two edges in the original graph meet at the same vertex, then draw an edge connecting the corresponding vertices in the new graph.