Problem 1 Recall that we defined binary trees in class as either

• A node with no children.

• A node with a left child that is a binary tree, and no right child.

• A node with a right child that is a binary tree, and no left child.

• A node with left and right binary-tree children.

Consider the following recursive definition of the height of a binary tree:

• The height of a node with no children is 0

• The height of a tree on a node with children is one more than the maximum of its children’s heights.

Prove that a tree of height h contains at most 2^{h+1} − 1 nodes.

Solution.

The proof is by structural induction on the definition of binary tree.

Base Case: A tree consisting of one node with no children has height h = 0. So 1 ≤ 2^{h+1} − 1 = 1.

Inductive Steps: We have three cases corresponding to the three cases of the definition:

• If the tree T is a node with a left child but no right child, let L be the left child binary tree and let h be its height. By inductive hypothesis, the tree L has at most 2^{h+1}−1 nodes. The height of tree T is h + 1, and the number of nodes in T is at most 1 + 2^{h+1} − 1 = 2^{h+1} < 2^{h+2} − 1.

• If the tree T is a node with a right child but no left child, it is analogous to the previous case.

• If the tree T is a node with both a left and right child L and R, then let h_{1} and h_{2} be the heights of the trees L and R respectively. Let also h be the maximum of h_{1} and h_{2}. By inductive hypothesis the trees L and R have at most 2^{h_{1}+1}−1 ≤ 2^{h+1}−1 and 2^{h_{2}+1}−1 ≤ 2^{h+1}−1 nodes. So, the number of nodes in T is at most 1 + (2^{h+1} − 1) + (2^{h+1} − 1) = 2^{h+2} − 1 = 2^{h′+1} − 1 nodes, where h′ = h + 1 is the height of T.

Problem 2 Back in 1996, a group of young Harvard graduates founded the startup NewMoney.com in anticipation of the need for a new currency upon the colonization of Mars in the year 2001. The proposed form of currency, the Gork, was originally printed only as a $6-Gork coin and a $15-Gork paper bill. What quantities of money (in Gorks) can be formed from just this currency? Solution.

: Answer A. The answer is 6 and all multiples of three greater then or equal to 15.

We can prove this by strong induction on n where n = 3k for k = 2 and k ≥ 4.

: Answer B. First of all notice that if we can make n Gorks using only coins and bills then n = 6a + 15b = 3(2a + 5b) for some a and b, and therefore n must be a multiple of 3. We can make 6 Gorks using one coin, and we can make neither 3 nor 9 Gorks. We claim that we can make any other quantities n such that n ≥ 12 and 3|n. In other words, we can make 12 + 3k Gorks for all k ≥ 0. We will prove this statement first by strong induction and then by well-ordering.

(a) Prove by strong induction that these and no other quantities can be formed. Solution.

: Answer A. Base Cases: As base cases we take all n ≤ 15. Clearly, if n ≤ 15 then we can make 6 from one coin, 12 from two coins, and 15 from one bill.

Inductive Step: Let n ≥ 15 and assume that for all 15 < m < n we can make m Gorks out of coins and bills. Show that we can make n Gorks out of coins and bills.

If n > 15 then we know that n − 6 > 9 and by the base cases and the inductive hypothesis, we know that we can make n − 6 Gorks using only coins or bills. We can therefore make n Gorks by adding a coin, so we can make n Gorks out of coins and bills.

This completes the inductive step, so we know we can make n Gorks out of coins and bills where n = 6 or n ≥ 12 and n is a multiple of 3.

Now, we need to show that we cannot make any other amounts using only coins and bills. Take first the case of 3 Gorks: We clearly cannot make 3 Gorks because coins and bills are both larger than 3 Gorks. We also cannot make 9 Gorks, by inspection.

We cannot make amounts that are not divisible by 3 because any combination of coins, c, and bills, b, will give us d = 6c + 15b = 3(2c + 5b), which is clearly a multiple of 3 when c and b are natural numbers.

: Answer B. We prove that we can make 12 + 3k cents using dimes and quarters by strong induction on k.

Base cases (k = 0, 1) We can make 12 and 15 cents using two coins and one bill, respectively.

Inductive Step (k ≥ 2): Assume we can make 12 + 3h Gorks for all h < k. In particular we can make 12 + 3(k − 2) Gorks using coins and bills. Using one more coin, we can also make 12 + 3(k − 2) + 6 = 12 + 3k Gorks, completing the induction proof.

(b) Prove the same thing by well ordering Solution.

: Answer A. Let’s now prove the same thing using well-ordering.

To make the statement of the problem clearer we introduce some notation. Let P (n) be the predicate “(n = 10) ∨ (3|n ∧ n ≥ 20)′′, and let Q(n) be the predicate “we can make n Gorks using coins and bills”.

We claim that for all n, P (n) ↔ Q(n), i.e., we can make n cents if and only if n is 6 or a multiple of 3 not smaller then 12.

This time we will prove ∀n.P (n) → Q(n) and ∀n.Q(n) → P (n) separately.

We first prove that ∀n.P (n) → Q(n). Let S be the set of all n such that P (n) and ¬Q(n). We will show that S is empty. Assume for contradiction that S is not empty. By the well-ordering axiom, S has a minimum element m. Since P (m) is true, m is a multiple of 3, but we cannot make m Gorks using coins and bills. Notice that m must be greater then or equal to 18 because 6, 12 and 15 Gorks can be made using respectively 1, 2 coins or a bill. Let n = m − 6. We cannot make n Gorks using coins and bills because otherwise we could also make m = n + 6 Gorks using one more coin. So, Q(n) is false. Moreover, m ≥ 18 and therefore n ≥ 12. Since n is a multiple of 3, P (n) is true and n is in the set S contradicting the fact that m was the minimum element.

We now prove that ∀n.Q(n) → P (n). Let T be the set of all n such that Q(n) and ¬P (n). We will show that T is empty. Assume for contradiction that T is not empty. By the well-ordering axiom, T has a minimum element m. We have Q(m), so we can make m Gorks using coins and bills. We distinguish two cases:

• if we used at least one dime to make m, then we can also make n = m − 6 cents using one less dime, i.e., Q(n). Moreover, ¬P (n) because otherwise also m = n + 6 satisfies ≠ P (m) (if we add 6 to a multiple of 3 it will still be a multiple of 3). So, n ∈ T contradicting that m is minimum.

• if we didn’t use any coins to make m, then m = 15h and P (m) which contradicts m ∈ T.

: Answer B. We prove that we can make 12 + 3k cents using coins and bills by well ordering. Let S be the set of all k such that we cannot make 12 + 3k Gorks using coins and bills and assume for contradiction that S is not empty. By well-ordering, S has a minimum element m. m cannot be 0 or 1 because we can make 12 and 15 Gorks. Therefore, m ≥ 2 and m − 2 ≥ 0. We claim that m − 2 is in S. To prove this, notice that if we could make 12 + 3(m − 2) = 12 + 3m − 6 Gorks using coins and bills, then we could make also 12 + 3m Gorks using one more coin. But, this is impossible because m ∈ S. So, m − 2 ∈ S and m is not the minimum.

Problem 3 Let the relations R and S be binary relations on the set ℕ of natural numbers. Define R as follows: ∀(a, b) ∈ ℕ × ℕ(a, b) ∈ Riffamod4 = bmod4. Define S as follows: ∀(a, b) ∈ ℕ × ℕ(a, b) ∈ Riff2^{a} = b ∧ b ≤ 15.

(a) Prove that R is transitive. Solution.

∀ not done yet

(b) Prove that R is symmetric. Solution.

∀a ∈ ℕ we have that amod4 = amod4, as modulo is a defined to be a function (same input yields same output). Thus, ∀a ∈ ℕ(a, a) ∈ R.

(c) Suppose T = R ∩ S. Fully define the relation T. Solution.

T = R ∩ S = ∀(a, b) ∈ ℕ × ℕ(a, b) ∈ T iffamod4 = bmod4 = 0 ∧ b ≤ 15.

(d) Let W = S ∘ R. Prove that W is antisymmetric. Solution.

We know that ∀(a, c) ∈ W c ≤ 15. Thus, we can define a set B = {1, 2, 4, 8} where ∀b ∈ ℕb ∈ Biffb ≤ 15 ∧ b = 2forsomen ∈ ℕ. We can now say that W ⊆ ℕ × B ⊆ ℕ × ℕ. Thus, ∀x ∈ ℕ∀y ∈ ℕxW y ∧ yW xiffx ∈ B ∧ y ∈ B. But there is no such (x, y) pair in W. The statement ∀x ∈ ℕ∀y ∈ ℕ (xW y ∧ yW x), so the requirement for antisymmetry is vacuously true.

(e) Find R ∘ S. Solution.

Let us define the set M_{i} ⊆ ℕ as {x|xmod4 = i}. Then, clearly there are 4 such sets, namely M_{0}, M_{1}, M_{2}, and M_{3}. Let (x, y) ∈ Z = R ∘ Siff(x = 0 ∧ y ∈ M_{1}) ∨ (x = 1 ∧ y ∈ M_{2}) ∨ ((x = 2 ∨ x = 3) ∧ y ∈ M_{0}). not done yet

Problem 4 Let R be the lexicographic ordering of strings of symbols from a totally ordered alphabet as defined in Rosen p. 417.

(a) Prove that R is a total order.

Solution.

We first show that R is a partial order. Reflexivity is clear from the definition. To show antisymmetry, suppose that a_{1} … a_{m} < b_{1} … b_{n}, and let t = min(m, n). This means that either a_{1} … a_{t} = b_{1} … b_{t} and m < n, so that b_{1} … b_{n} ≮ a_{1} … a_{m}, or else a_{1} … a_{t} < b_{1} … b_{t}, so that b_{1} … b_{t} a̸_{1} … a_{t} and hence again b_{1} … b_{n} a̸_{1} … a_{m}. Finally for transitivity, suppose that a_{1} … a_{m} < b_{1} … b_{n} < c_{1} … c_{p} . Let t = min(m, n), r = min(n, p), s = min(m, p), and l = min(m, n, p). Now if a_{1} … a_{l} < b_{1} … b_{l} < c_{1} … c_{l} then clearly a_{1} … a_{m} < c_{1} … c_{p}. Otherwise, without loss of generality we may assume that a_{1} … a_{l} = b_{1} … b_{l}. If l = t then m < n and m ≤ p. Furthermore, either b_{1} … b_{r} < c_{1} … c_{r} or b_{1} … b_{r} = c_{1} … c_{r} and n < p. In the former case, if r > l, then since p > m we have a_{1} … a_{m} < c_{1} … c_{p}, whereas if r = l then a_{1} … a_{l} < c_{1} … c_{l}. In the latter case, a_{1} … a_{s} = c_{1} … c_{s} and m < p, so again a_{1} … a_{m} < c_{1} … c_{p}. If l < t, then we must have b_{1} … b_{l} < c_{1} … c_{l}, whence a_{1} … a_{l} < c_{1} … c_{l}. Finally, the fact that R is a total order follows trivially from the definition of a lexicographic order and noticing that the strings of symbols are taken from a totally ordered alphabet.

(b) Prove that neither R nor R^{−1} is a well-ordering.

Solution.

Consider the alphabet {a, b} with a ⪯ b. Then R is not a well ordering since {b, ab, aab, aaab, aaaab, … } has no least element. Moreover, R^{−1} is not a well-ordering since {a, aa, aaa, aaaa, … } has no least element.

Problem 5 Define u_{n} recursively by

u_{0} = 2,  u_{1} = 3,  u_{n} = 3u_{n−1} − 2u_{n−2} for n ≥ 2 .

Prove that u_{n} = 2^{n} + 1 using

(a) strong induction, Solution.

(b) well ordering, Solution.

(c) weak induction. Solution.

Of course, the algebra in each of these three proofs will be similar, but the logic will differ. Do not use the fact that these three induction methods are equivalent.

Problem 6 Prove that in any undirected graph, the sum of the squares of the vertex degrees is even, or provide a counterexample. Solution.

Note that ∀d ∈ range(degree)d ≥ 0. We first prove that ∑_{v∈V} (degree(v))^{2} is even iff ∑_{v∈V} degree(v) is even. We argue that ∀x ∈ ℕx^{2} is even iff x is even. Furthermore, we can show that for any sum of non-negative naturals that sum is even iff there is an even number of odd terms in the sum. Since we have shown that the number of odd terms has not changed from the former sum to the latter sum, the problem can be reduced to dealing with the latter sum (henceforth, the “sum”). We know that there is an integral number of edges in the graph. For each edge, we count it twice in the sum. Therefore, sum_{v∈V} degree(v) = 2 |E|, which is clearly even. The sum of the squares of the vertex degrees is even for any undirected graph.

Problem 7 Prove that the vertices of an undirected graph can be colored either red or blue such that at least half of the neighbors of every red vertex are blue and at least half of the neighbors of every blue vertex are red. (Hint: Associate a value with each coloring, and use well ordering on the set of possible values.) Solution.

not done yet

Problem 8

(a) In how many ways can fourteen indistinguishable balls in five distinguishable boxes given no restraints on capacity of the boxes. Solution.

This is the normal stars and bars, for n bins (bars) r balls (stars). \binom{(n+r−1)}{r} = \binom{(5+14−1)}{14} = \binom{18}{14} =

\binom{18}{4}

(b) Consider the case where you want to place fourteen distinguishable balls in five distinguishable boxes given no restraints on the capacity of boxes. Solution.

\frac{factorial(18)}{factorial(4)}

(c) Now count the number of ways to place fourteen indistinguishable balls in five distinguishable boxes given that each box contains at least one and at most five balls. Solution.

You can first remove 5 balls from the game since each box contains at least one ball, and the new requirements become boxes containing at least 0 and at most 4 balls. We are now left with placing 9 balls into 5 boxes. Let’s ignore the capacity limit for the moment. We have 5^{9}. Now we need to subtract from that each of the cases where we have more than 4 balls in a particular box. There are \binom{4}{1} combinations of boxes that could have more than 4 balls at the same time, since at most one can have more than 4. Thus we want to subtract can’t compile formula

\binom{4}{1} ∑_{i=0}^{4} 5^{i}

. The total number of combinations is can’t compile formula

5^{9} − 4 ∑_{i=0}^{4} 5^{i}

. Problem 9 Find the coefficients of each of the following terms in the given polynomial expansion that follows:

(a) x^{4} in (2 + x)^{13} Solution. \binom{13}{4}2^{4}

(b) x^{2}5 in (2x + 3\frac{x}{)}^{46} Solution. \binom{46}{28}2^{28}3^{46−28}

(c) x^{7}y^{1}2 in (4x + 5y)^{19} Solution. \binom{19}{7}(4^{7})(5^{12})

(d) x^{3}y^{4} in (2x + 4y^{2})^{5} Solution. 2^{3}(4^{2})\binom{5}{3} Problem 10 Let n, r ∈ ℕ. Use the binomial theorem to evaluate the expressions in closed form (a)

∑_{k=0}^{n} \binom{n}{k}r^{k}

Solution. Equivalent to

∑_{k=0}^{n} \binom{n}{k}(r^{k})(1^{n−k}) = (1 + r)^{n}

(b) and

∑_{k=0}^{n} \binom{n}{k}(−r)^{k}

Solution.

Again, as before, at the term 1^{n−k} to each term in the sum. (1 − r)^{n}

(c) Use your analysis to conclude that if r is odd, then

2^{n−1} | ∑_{{k=0 \atop k even}}^{n} \binom{n}{k}r^{k} .

Note that if r = 1, this sum simply counts the number of even-sized subsets of an n-set, which we know is exactly 2^{n−1}. Solution.

not done yet

Problem 11 Using recently acquired probability skills from 6.042, Theory Moose has been at the casino ever since he turned in his last problem set. However, he feels the dealers are on to him and he skips town to buy out a department store and a plane ticket to paradise (aka 6.046). Theory Moose must act quickly to choose his new wardrobe from the department store, but before he can make a decision he stops to solve one more problem. Theory Moose is taking 6 tshirts, 4 pairs of shorts, and, of course, a pair of shades. How many different combinations of colors can he come up with given the following constraints:

The department store has the following colors available for each of the eleven items, with replacement: red, green, white, and black.

If he takes black-frame shades, at least 2 of the shorts he takes must be white.

If he is taking more than 3 red tshirts he won’t take any green with him at all.

Solution.

There are four colors from which to choose for items. If Theory Moose chooses enough red tshirts, his choices are constrained to not be green. There are 4^{6} combinations of tshirts if they can be any combination at all of the four colors. Suppose Theory Moose chooses all his red tshirts first. If he has more than 3 red tshirts the rest can’t be green. We say we are “uncounting” when Theory Moose has at least 4 red tshirts. The number of valid tshirt combinations given that we are “uncounting” is 6. The number of invalid tshirt combinations given that we are “uncounting” is 4. The total number of tshirt combinations for which we are “uncounting” is 6 + 4 = 10.

Let us consider the special situation where we are “uncounting”. If he has black shades, the number of combinations of shorts left is 3^{2}. If he has shades of the remaining 2 colors, the number of combinations of shorts left is 3^{4}. Thus, the total number of combinations of shorts-and-shades choices when we are “uncounting” is 3^{2} + 2(3^{4}) = 171. The total number of choices we want to keep even though we are “uncounting” is thus 3^{2}(171) = 1539.

Now let us consider the situation where we are not “uncounting”. In this case we have no restraints on the shorts-and-shades combinations other than those imposed on themselves. If Theory Moose takes black shades, the number of combinations of shorts left is 4^{2}. If Theory Moose takes one of the other 3 colors of shades, the number of combinations of shorts is 4^{4}. Thus the total number of combinations of shorts-and-shades choices when we are not “uncounting” is 4^{2} + 3(4^{4}) = 784. The total number of choices we should count when we are not “uncounting” is thus (4^{6} − 10)784 = 3203424.

Therefore, the total number of outfits Theory Moose can wear to Paradise is 1539 + 3202424 = 3204963.

Problem 12 The least common multiple of two natural numbers, m and n is defined to be the smallest natural number k such that m|k and n|k. It is denoted by lcm(m, n). Prove that every pair of natural numbers has a least common multiple. Using unique factorization, show that a · b = gcd(a, b) · lcm(a, b).

Solution.

Let m and n be any two natural numbers. Let M be the set of multiples of m and N the multiples of n. Consider M ∩ N. It is nonempty since it contains mn. By the well-ordering principle it contains a least element which is the least common multiple of m and n. Hence every pair of natural numbers has a least common multiple.

Let a = ∏_{i}p_{i}^{α_{i}} and b = ∏_{i}p_{i}^{β_{i}} where p_{1}, p_{2} … are the primes in increasing order. Following

Theorem 7.12 in Handout 13, Notes 4, it was shown that gcd(a, b) = ∏_{i}p_{i}^{min(α_{i},β_{i})}. By an identical

argument it can be seen that lcm(a, b) = ∏_{i}p_{i}^{max(α_{i},β_{i})}. Now, from the fact that for any α and β, α + β = max(α, β) + min(α, β), it follows that a · b = gcd(a, b) · lcm(a, b).

Problem 13 Find the flaws in the following “proofs.”

(a) CLAIM: a^{n} = 1 for all nonnegative integers n, whenever a is a nonzero real number.

BASIS STEP: a^{0} = 1 is true by the definition of a^{0}.

INDUCTIVE STEP: Assume that a^{k} = 1 for all nonnegative integers k with k ≤ n. Then note that a^{n+1} = \frac{a^{n}·a^{n}}{a^{n−1}} = \frac{1·1}{1} = 1.

Solution.

The flaw is that we should prove both n = 0 and n = 1 as bases cases because the inductive step uses the previous two values of n. Clearly a^{1} = 1 is not true, unless a = 1, and therefore the proof is wrong.

(b) CLAIM: \sqrt{2} is rational.

PROOF: Well-ordering. Let S be the set of all rational numbers greater than or equal to \sqrt{2}. This set contains a least element r by well-ordering. If this element is not \sqrt{2}, then there is another rational element between \sqrt{2} and r (by denseness of the rationals), implying r is not the smallest, a contradiction. Thus we must have r = \sqrt{2}.

Solution.

The flaw is that the well-ordering principle does not hold for the rationals, so we cannot use it to conclude that the above set has a minimum.

(c) CLAIM: every number can be described in a phrase of less than eighty characters.

PROOF: Well-ordering. Let S be the set of numbers that cannot be described in a phrase of less than eighty characters. If it is nonempty, it contains a smallest element. This is “The smallest number that cannot be described in less than eighty chracters.” This is a description of that number in less than eighty characters, a contradiction. Since the assumption that S was nonempty yields a contradiction, S must be empty and the claim is proved.

Solution.

The flaw in the above proof is that the set of numbers that can be described in less than eighty characters, is not a well-defined set.

Problem 14 [10 pts]

The graphs C_{n}, Q_{n}, W_{n}, and K_{n,m} are defined in Rosen 7.2.

(a) Describe the adjacency matrix for C_{n}.

For C_{n}, we label the vertices so that the cycle goes v_{1}, v_{2}, …, v_{n}, v_{1}. Then the matrix has 1’s on the diagonals just above and below the main diagonal and in positions (1, n) and (n, 1), and 0’s everywhere else.

(\begin{matrix}0 & 1 & 0 & 0 & … & 0 & 1 \\ 1 & 0 & 1 & 0 & … & 0 & 0 \\ 0 & 1 & 0 & 1 & … & 0 & 0 \\ 0 & 0 & 1 & 0 & … & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & … & 0 & 1 \\ 1 & 0 & 0 & 0 & … & 1 & 0 \end{matrix})

(b) Describe the adjacency matrix for K_{n,m}.

Vertices of K_{n,m} are partitioned into a group of n vertices and a group of m vertices. In this graph, an edge is present between two vertices if and only if the two vertices are from different groups. Therefore, the adjacency matrix of K_{n,m} consists of four sub-matrices. The top left and the bottom right matrices consist of 0’s with size n ∗ n and m ∗ m respectively. The top right and the bottom left matrices consist of 1’s with size of n ∗ m and m ∗ n respectively.

(\begin{matrix}0 & … & 0 & 1 & … & 1 \\ ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ 0 & … & 0 & 1 & … & 1 \\ 1 & … & 1 & 0 & … & 0 \\ ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ 1 & … & 1 & 0 & … & 0 \end{matrix})

(c) Give a simple recursive definition of the adjacency matrix for the graph Q_{n+1}. Hint: Use the matrix of Q_{n} and suitable identity matrices.

The base case is,

Q_{1} = (\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix})

Then, every Q_{n+1} (n ≥ 1) is defined inductively. The size of Q_{n+1} is 2^{n+1} ∗ 2^{n+1} and the left top and right bottom quarter of the matrix are Q_{n}, which correspond to the two subgraphs Q_{n} in Q_{n+1}. The right top and left bottom quarter of the matrix are identity matrices of size 2^{n} ∗ 2^{n}(I_{2^{n}}), which correspond to the edges connecting vertices k and k + 2^{n} for 0 ≤ k < 2^{n}, which differ by the most significant bit only.

Q_{n+1} = (\begin{matrix}Q_{n} & I_{2^{n}} \\ I_{2^{n}} & Q_{n} \end{matrix})

Problem 15 Let R be any relation. Prove that any relation that contains R and is reflexive (resp. symmetric, transitive) contains the reflexive (resp. symmetric, transitive) closure of R. This means the closure is the ”smallest” containing set that has the property.

Solution.

Problem 16 Each bead on a bracelet with three beads is either red, white, or blue as illustrated in the example shown. Define the relation R between bracelets as follows: (B_{1}, B_{2}), where B_{1} and B_{2} are bracelets, belongs to R if and only if B_{2} can be obtained from B_{1} by rotating it or rotating it and then reflecting it.

• Show that R is an equivalence relation.

• What are the equivalence classes of R?

Problem 17 Definition: Let S be a set. Let R be a subset of S × S. R is an equivalence relation if it satisfies the following properties

1. ∀a ∈ S, (a, a) ∈ R (reflexivity).

2. If (a, b) ∈ R, then (b, a) ∈ R (symmetry).

3. If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R (transitivity).

Definition: Let R be an equivalence relation on S. For a ∈ S, we define the equivalence class of a to be the set [a]_{R} = {b ∈ S|(a, b) ∈ R}.

For example, the relation R defined by (a, b) ∈ R if a ≡ b mod 4 is an equivalence relation on ℤ. There are four equivalence classes for this relation, namely:

• [0]_{R} = {z ∈ ℤ|z ≡ 0 mod 4}

• [1]_{R} = {z ∈ ℤ|z ≡ 1 mod 4}

• [2]_{R} = {z ∈ ℤ|z ≡ 2 mod 4}

• [3]_{R} = {z ∈ ℤ|z ≡ 3 mod 4}

(a) Let G be a simple graph. Define a relation R on the set of vertices V of G by (v, u) ∈ R, if there is a path connecting u to v.

Verify that R is an equivalence relation.

Solution.

• Reflexivity:

R is reflexive because trivially every vertex is connected to itself.

• Symmetry:

Suppose there is a path (u, x_{1}), (x_{1}, x_{2}), …, (x_{n}, v) connecting u to v. Then, the path (v, x_{n}), …, (x_{1}, u) connects v to u. Therefore, R is symmetric.

• Transitivity:

Let the path (u, x_{1}), (x_{1}, x_{2}), …, (x_{n}, v) connect u to v, and the path

(v, y_{1}), (y_{1}, y_{2}), …, (y_{m}, w) connect v to w.

Then the path (u, x_{1}), …, (x_{n}, v), (v, y_{1}), …, (y_{m}, w) connects u to v.

Therefore R is transitive.

(b) What are the equivalence classes of R?

Solution.

The equivalence classes of R are the connected components of G.

Problem 18 A relation R on a set A is weakly transitive if for all a, b, c, d ∈ A, the relations aRb, bRc, and cRd imply the relation aRd.

Prove or disprove the following statements.

(a) Every symmetric, weakly transitive relation is transitive.

Solution.

The claim is false. The diagram below shows a counterexample.

(b) Every reflexive, symmetric, weakly transitive relation is an equivalence relation.

Solution.

Proof. The relation R is an equivalence relation if it is reflexive, symmetric, and transitive. The first two properties hold by assumption; all that remains is to show that R is a transitive relation. Suppose that the relations aRb and bRc hold. Because R is reflexive, the relation aRa also holds. Because R is weakly transtive, the relations aRa, aRb, and bRc imply the relation aRc. Therefore, R is transitive.

Problem 19 Let the relations R and S be binary relations on the set ℕ of natural numbers. Define R as follows: ∀(a, b) ∈ ℕ × ℕ(a, b) ∈ Riffamod4 = bmod4. Define S as follows: ∀(a, b) ∈ ℕ × ℕ(a, b) ∈ Riff2^{a} = b.

(a) Prove that R is transitive.

(b) Prove that R is symmetric.

(c) Find R ∩ S.

(d) Let T = S ∘ R.

Problem 20 (15 points) This problem concerns Hamiltonian circuits in n-cubes. A Hamiltonian circuit in a graph is a circuit traversing every vertex in the graph exactly once. The n-cube is defined on page 448 of Rosen (p. 441 in ed. 3). (Rosen also uses the name Q_{n} for an n-cube.) However, the following recursive definition of an n-cube is equivalent to the one given in Rosen, but may simplify your solutions. A 0-cube is a single vertex. An (n + 1)-cube consists of two n-cubes with corresponding vertices joined by edges. For example, a cube is two squares with corresponding corners joined.

(a) Draw a 4-cube.

Solution.

(b) In your drawing, highlight a Hamiltonian circuit.

Solution.

The dotted edges in the diagram above form a Hamiltonian circuit.

(c) Use induction on n to prove that an n-cube has a Hamiltonian circuit for all n ≥ 2.

Solution.

The proof is by induction. Let P (n) be the proposition that an n-cube has a Hamiltonian circuit. In the base case, P (2) is true, because a 2-cube is itself a cycle.

In the inductive step, assume that an n-cube has a Hamiltonian circuit to prove that an (n+1)-cube has a Hamiltonian circuit. Regard an (n+1)-cube as two n-cubes with corresponding vertices joined. The first n-cube has a Hamiltonian circuit H by induction, and there is a matching Hamiltonian circuit H′ in the second n-cube.

Take an edge (u, v) ∈ H and the corresponding edge (u′, v′) ∈ H′. We can construct a Hamiltonian circuit in the (n + 1)-cube by starting at vertex u, traversing the circuit H all through the first n-cube until reaching vertex v, crossing the edge (v, v′), traversing the circuit H′ all through the second n-cube until reaching vertex u′, and then crossing the edge (u′, u).

Problem 21 [30 pts]

Definition: A simple graph, G, has inherited degree d ≥ 0 if and only if

(i) every vertex of G has degree ≤ d, or (ii) there is a vertex v ∈ G of degree ≤ d, and the subgraph of G obtained by removing v has inherited degree ≤ d.

(a) Prove that W_{n} has inherited degree 3.

Solution.

We use the induction on n. Let P (n)::= W_{n} has inherited degree 3.

Base Case: W_{3} has four vertices of degree 3 and it has inherited degree 3 by definition (i).

Inductive Step: Assume P (n) is true, we need to prove P (n + 1). W_{n+1} has n + 1 vertices of degree 3 and 1 vertex of degree n + 1. The graph G obtained by removing a vertex of degree 3 has n − 2 vertices of degree 3, 2 vertices of degree 2 and 1 vertex of degree n. We can also obtain G by removing a edge between two vertices of degree 3 in W_{n}. Since W_{n} has inherited degree 3 by inductive hypothesis and removing an edge does not increase the degree of vertices, G has inherited degree 3. Then, by definition (ii), W_{n+1} has inherited degree 3.

Therefore, we prove that W_{n} has inherited degree 3 for ∀n ≥ 3.

(b) Prove that a tree has inherited degree 1.

We use the definition of tree in Rosen, 8.1: a tree is a connected undirected graph with no simple circuits. Also, we only consider trees with a finite number of vertices.

Solution.

We need to prove two facts here. First we have to prove that every tree with at least two vertices has a leaf (a leaf is a vertex of degree one). Then we need to show that the subgraph constructed by removing one leaf is still a tree.

First, let’s prove that every tree with at least two vertices has a leaf. Let T be a tree, and let P be a longest simple path in T. In a finite graph, a path of length greater than or equal to the the number of vertices must visit some vertex more than once. So a simple path must be shorter than the number of vertices. Therefore in any finite graph there must be longest simple path. (We’re using the Wellordering principle here, taking the least element of {|V | − k : k is the length of a simple path}.)

Suppose P = (v_{1}, v_{2} …, v_{k}), we claim that v_{1} is a leaf. For if not, there will be an edge {v, v_{1}} in T where v ≠ v_{2}. The vertex v cannot occur in P, for otherwise this creates a cycle, which contradicts that the graph is a tree. Therefore, P′ = (v, v_{1}, v_{2} …, v_{k}) is also a simple path in the tree and P′ is longer than P. But this is a contradiction because we have assumed that P is the longest path in the tree. As a result, a tree with 2 or more vertices has to have a leaf.

Second, let’s prove that the subgraph constructed by removing one leaf is still a tree. From the definition given in the book (cf. Rosen p531), a tree is a connected undirected graph with no simple circuits. Removing a leaf from a tree does not create any circuit. Also, since the leaf has degree 1, it is not connecting any other two vertices in the tree. Therefore, after removing the leaf, no vertices get disconnected. In other words, the subgraph is still connected. Since the subgraph is a connected undirected graph with no simple circuits, it is also a tree.

Since every tree has a leaf(vertex with degree 1) and the subgraph is still a tree after removing a leaf, we can apply the same method in the previous part to show that a tree has inherited degree 1.

(c) Prove that if a graph has inherited degree d, then it is (d + 1)-colorable.

Solution.

We use induction on the number of vertices in a graph to prove this fact.

Let P (n)::= “∀d > 0, any n-vertex graphs with inherited degree d is (d + 1) colorable.”

Base Case: n = 1. There is only one 1-vertex graph. And it is obviously (d+1) colorable (∀d > 0).

Inductive Step: Assume that P (n) is true, we need to prove P (n + 1) is true. Given any (n + 1)- vertex graph G with inherited degree d for any d > 0, there are 2 possible cases:

1. All vertices in G has degree ≤ d. Then it is (d + 1)-colorable, as proved in the lecture.

2. There is a vertex v ∈ G of degree ≤ d, and the subgraph G′ obtained by removing v has inherited degree d. Since G′ has n nodes and has inherited degree d, by inductive hypothesis G′ is (d + 1) colorable. Now consider the vertex v. Since it has degree ≤ d, it has at most d neighbors and therefore it can be colored with the (d + 1)^{st} color which is different from all of its neighbors.

Therefore, by induction, every graph with inherited degree d is (d + 1)-colorable.

(d) For every n > 0, describe an example of a graph which does not have inherited degree n, but which is 2-colorable.

Solution.

An example would be K_{n+1,n+1}. Every vertex in K_{n+1,n+1} has degree n + 1. Therefore, it does not have inherited degree n. However, it is 2-colorable since every complete bipartite graph is 2-colorable.