Name:      

Directions: Show all work.

1. [3 parts, 2 points each] Let $G$ be the Petersen graph. Recall that $V(G)$ is the set of $2$-element subsets of $\{1,2,3,4,5\}$ with $\mathit{𝑢𝑣}\in E(G)$ if and only if $u$ and $v$ are disjoint.

   

   1. Is $G$ bipartite? Prove your answer is correct.

   2. Recall that $P_n$ is the path with $n$ vertices. Let $k$ be the maximum integer such that $P_k$ is a subgraph of $G$. Determine $k$ and find a copy of $P_k$ as a subgraph of $G$. No proof required.

      

   3. Let $t$ be the maximum integer such that $P_t$ is an induced subgraph of $G$. Determine $t$ and find a copy of $P_t$ as an induced subgraph of $G$. No proof required.

      

2. [2 parts, 2 points each] Graph Ramsey Problems.

   1. Prove that $K_5\to ̸(P_5,P_5)$.
   2. Recall that $C_n$ is the $n$-vertex cycle. Use the fact that $K_6\to (C_4,C_4)$ to prove that $K_6\to (P_5,P_5)$.