1. Solve each of the following (unrelated) problems: a. Suppose in a bipartite graph all the vertices except one have the same degree d, and the remaining vertex has degree x. Show that x must be a multiple of d. b. Define a simple graph Rk on vertex set of Qk by making two binary k-tuples adjacent iff they agree in exactly one coordinate. Prove that Rk is isomorphic to Qk if and only if k is even. 2. Show that each edge in the Petersen graph belongs to exactly four 5-cycles. Use this to show that the Petersen Graph has exactly twelve 5-cycles. What are the maximum number of edges in a bipartite subgraph of the Petersen graph?

Fig: 1