Umass Amherst Logic Chapter 1 Four Color Theorem Problem

Description

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.

Tags:
positive integers

Pythagorean

Four Color Theorem

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.