Name:      

Directions: Show all work.

1. [2 points] Give a list of distinct integers of maximum possible length that does not contain an increasing subsequence of length $5$ or a decreasing subsequence of length $4$.
2. [2 points] Give a formula for the number of edges in the $n$-vertex complete graph $K_n$. Prove that your answer is correct.

3. [2 points] Construct a $6$-vertex bipartite graph with $9$ edges.

4. [2 points] Are the following graphs isomorphic? If so, then give an isomorphism. If not, then give a property that distinguishes the graphs.

      

5. [2 points] Let $G$ be an $n$-vertex $m$-edge graph. Prove that $G$ contains a vertex $u$ whose degree $d(u)$ is at least $2m∕n$.