1. Suppose that T is a tree. We can turn T into a rooted tree by designating one of the vertices to be the root. Show, that different choices of root may turn the same tree into a rooted tree of height 5 or of height 9. 2. Suppose T is a tree with the property that each vertex of T either has degree 1 or degree 5. Show that the number of vertices of T cannot be a multiple of 4. 3. Each of the following proofs has (at least one) flaw in its reasoning. Identify the flaw in the reasoning. Note that when we say a flaw in the reasoning, the flaw must occur within the proof of the claim, and not in the claim itself . Some of these claims are true, and some of them are false - but all of the proofs are flawed. (a) Claim: A graph G cannot have an odd number of vertices of degree 5. Proof: If there are 2k + 1 vertices of degree 5, then the sum of their degrees is 5(2k +1) = 10k + 5 which is an odd number. But the sum of the degrees of vertices in a graph must be even, so this is impossible. (b) Claim: Suppose G is a graph with three vertices of degree 2, one vertex of degree 3, and three vertices of degree 1. Then G must be a tree. Proof: The sum of the degrees of G is 2 x 3+3 x 1+1 x 3 = 12, and therefore there are six edges. But there are seven vertices. Because there is one more vertex than there are edges, the graph is a tree: we've seen that any tree with n vertices must have n-1 edges. (c) Claim: If n is an integer such that n % 32 = 16, then n % 32 = 0. Proof: n % 32 = 16, so we have n = 16(mod 32), and therefore n = 4(mod 32). But then n = 4 (mod 32), which means n = 64(mod 32)), so n = 0(mod 32), and hence n % 32 = 0. (d) Claim: The largest positive integer ends in 0. Proof: Suppose that k is a positive integer. We will show that if k does not end in zero, then it cannot be the largest positive integer (and therefore that the largest positive integer must end in 0). For if k does not end in 0, consider 10k. This integer does end in 0, because it is a multiple of 10, and is also larger than k. Therefore the largest positive integer must end in 0. 4. Give a direct proof to show that if n is an integer such that 4n = 20 (mod 32), then n = -7 (mod 16). 5. Give a direct proof to show that if n is an integer such that n divides 12 and n divides 8, then n also divides 4. 1. Suppose that T is a tree. We can turn T into a rooted tree by designating one of the vertices to be the root. Show, that different choices of root may turn the same tree into a rooted tree of height 5 or of height 9. 2. Suppose T is a tree with the property that each vertex of T either has degree 1 or degree 5. Show that the number of vertices of T cannot be a multiple of 4. 3. Each of the following proofs has (at least one) flaw in its reasoning. Identify the flaw in the reasoning. Note that when we say a flaw in the reasoning, the flaw must occur within the proof of the claim, and not in the claim itself . Some of these claims are true, and some of them are false - but all of the proofs are flawed. (a) Claim: A graph G cannot have an odd number of vertices of degree 5. Proof: If there are 2k + 1 vertices of degree 5, then the sum of their degrees is 5(2k + 1) = 10k +5 which is an odd number. But the sum of the degrees of vertices in a graph must be even, so this is impossible. (b) Claim: Suppose G is a graph with three vertices of degree 2, one vertex of degree 3, and three vertices of degree 1. Then G must be a tree. Proof: The sum of the degrees of G is 2 x 3 + 3 x 1+1 x 3 = 12, and therefore there are six edges. But there are seven vertices. Because there is one more vertex than there are edges, the graph is a tree: we've seen that any tree with n vertices must have n-1 edges. (c) Claim: If n is an integer such that n % 32 = 16, then n % 32 = 0. Proof: n % 32 = 16, so we have n = 16(mod 32), and therefore n = 4(mod 32). But then n = 4 (mod 32), which means n = 64(mod 32)), so n = 0(mod 32), and hence n % 32 = 0. (d) Claim: The largest positive integer ends in 0. Proof: Suppose that k is a positive integer. We will show that if k does not end in zero, then it cannot be the largest positive integer (and therefore that the largest positive integer must end in 0). For if k does not end in 0, consider 10k. This integer does end in 0, because it is a multiple of 10, and is also larger than k. Therefore the largest positive integer must end in 0. 4. Give a direct proof to show that if n is an integer such that 4n = 20 (mod 32), then n = -7 (mod 16). 5. Give a direct proof to show that if n is an integer such that n divides 12 and n divides 8, then n also divides 4.