Name:      

Directions: Show all work. No credit for answers without work.

1. [5 points] Short answer: what is the maximum size of a list of distinct integers with no increasing sublist of size $10$ and no decreasing sublist of size $7$?
2. [10 points] Let $S=\{1,2,3,4,5,6,7,8\}$. Prove that if $T$ is a subset of $S$ of size $5$, then $T$ contains a pair of integers that sum to $9$.

3. [10 points] Let $A=\{1,\dots ,n\}$, $B=\{n+1,\dots ,2n\}$, and $C=\{2n+1,\dots ,3n\}$. Prove that if $n\ge 15$, then there exists $a_1,a_2\in A$, $b_1,b_2\in B$, and $c_1,c_2\in C$ such that $(a_1,b_1,c_1)\ne (a_2,b_2,c_2)$ and $a_1^2+b_1^2+c_1^2=a_2^2+b_2^2+c_2^2$.

4. [2 parts, 10 points each] In a checkerboard, a diagonal is a maximal set of cells whose centers are on a line with a slope of $1$ or $-1$. Two examples of diagonals follow.

      

   1. Show that it is possible to mark $28$ cells of the $8\times 8$ checkerboard such that every diagonal contains at most $2$ marked cells. Four boards are given below for your convenience. Clearly indicate your final solution.

               

   2. Prove that no matter how $29$ cells are marked, some diagonal contains at least $3$ marked cells.

5. [2 parts, 10 points each] Graphs and degrees.

   1. Construct an $8$-vertex graph in which one vertex has degree $4$ and the rest of the vertices have degree $2$.
   2. Prove that there is no $8$-vertex bipartite graph in which one vertex has degree $4$ and the rest of the vertices have degree $2$. (Hint: suppose for a contradiction that $G$ is such a bipartite graph with parts $X$ and $Y$. What can you say about ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{v\in V(G)}d(v)$ and ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{v\in X}d(v)$?)

6. [10 points] Determine if $G$ and $H$ are isomorphic. If they are isomorphic, then give an isomorphism. If not, then give a property that distinguishes the graphs.

      

7. [25 points] Recall that $K_3$ is the triangle and $K_{1,3}$ is the complete bipartite graph with parts of sizes $1$ and $3$. Show that $r(K_3,K_{1,3})=7$. Be sure to show both that $r(K_3,K_{1,3})>6$ and $r(K_3,K_{1,3})\le 7$.