# Harrison Chapman

## 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.