1. In this question, G = (V, E) is a graph such that G has 10 vertices; G is 2-regular, i.e. each vertex has degree 2; G has no loops; G is planar but not necessarily connected. You might also find it helpful to remember Eulers formula: in a planar graph, |V | |E| + |F| = 1 + (G), where (G) is its number of connected components.

(a) Calculate |E|.

(b) Calculate |F|.

(c) How many different possible such graphs G are there (up to isomorphism)? Explain.

2. Recall that the n-dimensional hypercube Qn is the graph with 2n vertices labeled by all length n binary strings, and two vertices are joined by an edge if and only if their labels differ in exactly one digit.

(a) Draw the graphs Q2 and Q3.

(b) How many edges are there in Qn?

(c) Find a formula for the number of subgraphs of Qn that are isomorphic to Q2. [For example, the graph Q3 has exactly 6 subgraphs that are isomorphic to Q2 corresponding to the 6 faces in the usual three-dimensional cube.