Math as a Liberal Art - Mathematics 105 - Spring 2008

1. Suppose G is a connected graph. Determine which of the following statements imply which. Note: "open path" means "non-closed path", i.e., a path that's not a cycle.
   • p = "G has no odd vertices"
   • q = "G has exactly two odd vertices"
   • r = "G has more than two odd vertices"
   • s = "G has an Euler cycle"
   • t = "G has an open Euler path"
   • u = "G has an Euler path"

   Give your answers by filling out the following table (you may print out the table or draw your own). In each box, put a Y or N according to whether the letter above the box implies the letter to the left of the box. For example, p implies u, so we put a Y in the box under p and to the right of u; but u does not imply p, so we put an N under u to the right of p.

   	p	q	r	s	t	u
   p						N
   q
   r
   s
   t
   u	Y

    

2. Can a graph have both an Euler cycle and an open Euler path? If so, give an example; if not, explain why not.
3. Suppose you and your friend are detectives investigating a crime. There are two suspects; let's call them A and B. You prove that if A is innocent, then B is innocent too. Your friend proves that B is guilty. Can we conclude from this that A is guilty? Explain your reasoning very clearly.
4. The following questions are independent of each other; i.e., the p and the q in one question have nothing to do with the p and the q in another question (and nothing to do with the p and q in problem 1 above).
   1. Suppose you prove that statement p implies statement q; i.e., if p is true, then q is true. Suppose your friend proves that statement q is false. Can I conclude that p is false too? Explain your reasoning clearly.
   2. Suppose you prove that if p is true, then q is true too. Can I conclude that if q is true, then p is true? Explain your reasoning clearly.
   3. Suppose you prove that if p is true, then q is true too. Can I conclude that if q is false, then p is false? Explain your reasoning clearly.
   4. Suppose you prove that if p is false, then q is false too. Can I conclude that if q is true, then p is true? Explain your reasoning clearly.
5. Suppose I want to prove to you that the formula  1 + 2 + ... + n = n(n+1)/2  is correct. Is the following a valid proof? Explain why or why not.
        1 + 2 + 3 = 6; and 3(3+1)/2 = 12/2 = 6; so the formula works when n = 3. So the formula works for every number n.
6. Suppose I want to prove to you that the formula  1 + 2 + ... + n > 2^n   is wrong. Is the following a valid proof? Explain why or why not.
        1 + 2 + 3 = 6; and 2^3 = 8; but 6 is not greater than 8. So the formula doesn't work when n = 3. So the formula is not correct.