1. Suppose that T is a tree. We can turn T into a rooted tree by...

 

Transcribed Image Text:

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

Answer rating: 100% (QA)

The claim in the image is that a graph G cannot have an odd number of vertices of degree 5 This is t... View the full answer