2. Section 2.9: Problem 16 (a) and (e)

3. Show that the number of ways to choose a committee with a chair person (for the committee) from a group of $n$ people is equal to: $n 2^{n-1}$ (the size of the committee can be any number from $1$ to $n$).

$~~$ Also, use another way of counting to show that the same number is equal to: $\sum_{k=1}^n k {n \choose k}.$

$~~$ [Hint: To obtain the second formula, pick the committee of size $k$ and then pick a chair in the committee.]

4. Section 2.9: Problem 11

2. Section 2.9: Problem 30

$~~$ [Hint: The answer is in terms of multinomial numbers.]

3. Section 2.9: Problem 32

4. Section 2.9: Problem 33

5. Section 3.11: Problem 2

6. (Bonus problem) As in Example 3.1 consider a collection of $n$ (distinct) lines in the plane such that:

$~~~~~~~~~~~$ (a) any two of them intersect; $~~~$ (b) no three of them pass through the same point.

$~~$ Show that the regions in the plane created by these lines can be colored with two colors B and W such that no two neighboring regions have the same color.

$~~$ We say that two regions are neighboring if they have a line or line segment in common.

$~~$ [Hint: do this recursively.]

2. Section 3.11: Problem 16

3. Section 3.11: Problem 18

4. Section 4.6: Problem 1 (e), (g)

5. (Bonus problem) Section 3.11: Problem 20

2. Section 5.9: Problem 7

3. Section 5.9: Problem 8

4. Section 5.9: Problem 10

5. Section 5.9: Problem 12

$~~$ [Hint: use Theorem 5.5 about Hamiltonian graphs.]

2. Section 5.9: Problem 30

3. Section 5.9: Problem 38

4. Section 5.9: Problem 40

5. Prove that the chromatic number of a tree $T$ (with more than one vertex) is $2$.

2. Section 7.7: Problem 6

3. Section 7.7: Problem 16

4. Section 7.7: Problem 20

5. (Bonus problem) Section 7.7: Problem 22 (a)

2. Section 8.8: Problem 4 (b) and (e)

3. Section 8.8: Problem 5

4. Let $a_n$ be the number of ways that a number $n$ can be written as a sum of integers: $n = x_1 + x_2 + x_3 + x_4$, where $x_1 \geq 0, ~x_2 \geq 0, ~ x_3 \geq 1$ and $0 \leq x_4 \leq 1$.

$~~$ Write the generating function for $(a_n)$ in closed form. Find a formula for $a_n$ in terms of $n$.

5. Let $(b_i)$ be the sequence defined recursively by: $b_{i+2} = b_{i+1} + 2b_i$ and $b_0 = 1,~ b_1 = 1$.

$~~$ Find the generating function for this sequence.

1. (a) In the proof of Ramsey's theorem, we in fact showed that: $R(m, n) < R(m-1, n) + R(m, n-1)$.

$~~$ Using this inequality and material/examples discussed in class, show that $R(3, 4)$ is at most 9.

$~~$ (b) (Bonus problem) To show that $R(3, 4)$ is exactly 9 we need show that $R(3, 4) > 8$.

$~~$ To do this, we need to color the edges of the complete graph $K_8$ by two colors Red and Blue such that, there is no Red triangle and there is no $K_4$ subgraph which is Blue.

$~~$ Can you find such a coloring of edges of $K_8$?

$~~~~~~$ [Hint: the graph of Red edges is an $8$-gon with all its main diagonals, i.e. connect each vertex by Red to vertices before and after it as well as the vertex exactly opposite to it.]

2. One can define Ramsey numbers for more than two colors.

$~~$ The Ramsey number $R(n_1, ..., n_s)$ is the smallest number $r>0$ such that if we color the edges of a complete graph $K_r$ with $s$ colors $C_1, \ldots, C_s$ then there exists:

$~~~~$ * $~$ either a complete subgraph $K_{n_1}$ colored $C_1$,

$~~~~$ * $~$ or a complete subgraph $K_{n_2}$ colored $C_2$,

$~~~~$ * $~$ or ...

$~~~~$ * $~$ or a complete subgroup $K_{n_s}$ colored $C_s$.

$~~$ The generalized Ramsey theorem says that for any integers $n_1, \ldots, n_s$ such a number $r = R(n_1, ..., n_s)$ exists.

$~~$ Use the generalized Ramsey theorem to prove the following:

$~~$ For any $s \geq 2$, there is $r > 3$ such that for any coloring of the numbers $1,2,\ldots,r$ with $s$ colors, there are three integers $1 \leq x, y, z \leq r$ of the same color such that $x + y = z$.

$~~$ [Hint: let $n$ be the Ramsey number $R(3, 3, \ldots , 3)$ where $3$ is repeated $s$ times.

$~~$ Recall that $r = R(3,3,\ldots,3)$ has the property that if the edges of a complete graph $K_r$ are colored with $s$ colors then there is a triangle in $K_r$ all whose edges have the same color.

$~~$ Color the edges $(i, j)$ of $K_r$ as follows: assume $j>i$ then color the edge by the color $j-i$.]

1. Section 12.6: Problem 10: Prove that if no two weights are equal in a weighted simple graph, then there is a unique minimum weight spanning tree.

2. Section 12.6: Problem 11

3. Section 13.7: Problem 2

The three last problems of the semester