Math 301: Homework 12

Due: Friday, December 13, 2019

Note:

This homework assignment will not be collected or graded; it is here for practice and to give an example of a homework that we would have on the end-of-semester material.

Exercises:

  1. Draw a graph that is not 4-colorable but is 5-colorable.

    The complete graph \(K_5\) is 5-colorable but not 4-colorable.

  2. Show by example that if we don’t assume the triangle inequality, then a tour found by the Tree Shortcut Algorithm can be longer than 1000 times an optimal tour.

    Consider the cycle graph \(C_3\) with edge weights 1, 1, 4000. Then the optimal tour has cost \(2(1+1)=4\), but every TSA-produced tour has weight \(1+1+4000 = 4002 > 4000 = 1000*4\).

  3. Show that a planar graph \(G\) with 8 vertices and 13 edges cannot be 2-colored.

    By Euler’s theorem, \(G\) must have 7 faces. If all 7 faces had degree 4 or larger, then there would be at least \(7*4/2 = 14\) edges. But there are only 13 edges in \(G\), so at least one of the faces must be a triangle. So, \(G\) has an odd cycle (the triangle) and must not be 2-colorable.

  4. Explain why the following is true, or give a counterexample if it is false: Every planar graph can be 3-colored.

    This is false. \(K_4\) is planar, 4-colorable, and not 3-colorable.

  5. Let \(G\) be a connected graph such that all vertices but one have degree at most \(d\) (one vertex is allowed to have degree larger than \(d\)). Prove that \(G\) is \((d+1)\)-colorable.

    If no vertex of \(G\) has degree larger than \(d\), then the result is immediate by Brooks’s Theorem.

    On the other hand we will use induction. Let \(D \ge d+1\) be the degree of the one vertex \(v\) in the graph with degree larger than \(d\). If a graph has fewer then \((D+1)\) vertices this vertex cannot exist. So, consider any graph with \((D+1)\) vertices whose degrees are all less than \(d\) except for the vertex \(v\). The vertex \(v\) must be connected to all other vertices in the graph, so removing \(v\) yields a graph that has vertices all of which have degree at most \((d-1)\) and is by Brooks’s Theorem \(d\)-colorable. Take a \(d\)-coloring and reintroduce \(v\), coloring it with the \((d+1)\)st color.

    Now suppose that for some \(D+1 \le n\) we know that a graph of \(n\) vertices with a large vertex \(v\) of degree \(D\) and the rest degree \(\le d\) is \((d+1)\)-colorable. Consider a graph of \((n+1)\) vertices with this degree property, and let \(w\) be any vertex in the graph with degree \(\le d\). Removing \(w\) yields a graph of \(n\) vertices, and is by our inductive hypothesis \((d+1)\) colorable. Reintroducing \(w\), we see that \(w\) is connected to at most \(d\) different vertices of at most \(d\) different colors and hence there is a color with which we can color \(w\).

    Hence by induction, we are finished.