Directions: Solve the following problems. All written work must be your own. See the course syllabus for detailed rules.

1. Graphs, Subgraphs, and Isomorphism.

   1. Let $G$ be a graph. The neighborhood of a vertex $v\in V(G)$, denoted $N(v)$, is the set of all vertices adjacent to $v$. Show that the $4$-cycle $C_4$ is not a subgraph of $G$ if and only if for all distinct $u,v\in V(G)$, we have $|N(u)\cap N(v)|\le 1$. Note: a vertex $w$ in $N(u)\cap N(v)$ is a common neighbor of $u$ and $v$.
   2. Recall that the Petersen graph is the graph whose vertices are the $2$-element subsets of $\{1,2,3,4,5\}$ where $u$ and $v$ are adjacent if and only if $u\cap v=\varnothing$. Use part (a) to show that the Petersen graph does not contain a $4$-cycle.

   3. Use part (b) to give a short proof that the graph $H$ below is not isomorphic to the Petersen graph.

      

2. [2.3.2] Suppose that $r(4,5)=25$. Let $G$ be a copy of $K_{25}$ in which each edge is colored red or blue. Prove that $G$ either contains a monochromatic copy of $K_5$ (red or blue), or $G$ contains both a red copy and a blue copy of $K_4$.
3. [2.3.8] Prove that $r(3,4)>8$.