Overview
4. In class we talked about the Four Color Theorem: if X is a planar graph with a finite number of vertices, then X can be colored using only 4 colors R, B, G and Y . In other words, each vertex of the graph can be assigned R, B, G or Y so that when two vertices are joined by an edge, those two vertices must have different colors. Take a look at the graphs on the next page.
(a) Find a coloring of the graph labeled A that uses 4 colors. Also, explain why no fewer colors will work.
(b) Explain why the graph labeled B cannot be colored with 4 colors. This graph is, however, not planar. Explain why it does not violate the Four Color Theorem. It might be helpful to think about the truth table of P =⇒ Q.
5. In class we talked about Fermat’s Last Theorem. In this problem, we show that x 2 + y 2 = z 2 has an infinite number of positive integer solutions (x, y, z) where (x, y, z) have no common factors. We already know about the solutions (3, 4, 5) and (5, 12, 13) and perhaps (8, 15, 17) since they show up all the time in high school. We call a solution (x, y, z) to the equation a primitive Pythagorean triple when (x, y, z) have no common factors.
(a) Let a and b be two positive integers with a > b. Show that setting x = a 2 − b 2 , y = 2ab, and z = a 2 + b 2 give a solution to the equation x 2 + y 2 = z 2 .
(b) What values of a and b yield the three Pythagorean triples above?
(c) Try your best to argue that if a and b have a common prime factor p, then x, y, and z will all have p as a factor.
(d) What common factor will x, y, z share if a and b have the same parity, meaning they are both even or both odd?
(e) In fact, if we avoid the two situations above, then (x, y, z) will be primitive. Use this result to find an infinite number of primitive Pythagorean triples.
(f) (Bonus) In fact, every primitive Pythagorean triple is obtained by this method. The first step in proving this is to see that for any primitive solution (x, y, z), exactly one of x and y must be even. In particular, x and y cannot both be odd. In class (and in the book in Example 1.21), we saw that if x is odd, then x 2 − 1 is divisible by 8, or equivalently, x 2 is of the form 8k + 1 for some integer k. Use this result (a theorem) to show that if x and y are both odd, then x 2 + y 2 is even, but never divisible by 4. On the other hand, if z 2 = x 2 + y 2 and x and y are both odd, explain why z 2 is divisible by 4. Complete the proof that if x 2 + y 2 = z 2 , then x and y cannot both be odd.