CS/MATH 111 Final Sample Problems

Problem A1: Determine whether the two bipartite graphs below have a perfect matching. Justify your answer, either by showing a perfect matching or using Hall’s theorem to prove that it does not exist.

graph G

graph H

Problem A2: For each of the two graphs below, determine whether they are planar.   Justify

your answer:  if the graph is planar, show its planar embedding.  If the graph is not planar, use

Kuratowski’s theorem to justify it.

Problem A3: (a) Find strongly connected components of the digraph G given below. Justify the correctness of your solution.

(b) Is it possible to convert G into an acyclic digraph by reversing the direction of only one edge? Justify your answer.

Problem A4: For each graph below determine the minimum number of colors necessary to color its vertices. Justify your answer, by (i) giving a coloring and (ii) explaining why it is not possible to use fewer colors. You can represent colors by integers 1 , 2, 3, .... To show the coloring, draw the

graph, marking each vertex with its color.

G

Problem A5: For each graph G and H below, determine whether it has a hamiltonian cycle. Justify your answer, by showing the hamiltonian cycle if it exists, or proving that it does not exist.

G

H

Problem A6: For the digraph shown below, compute the number of paths of length 8 from vertex 1 to vertex 3.  You must use the method from class that uses adjacency matrices (other solutions will not be accepted), and you must show your work.

G

1

Problem A7: Let G be a graph with 10 vertices and four vertices of degree 8.  Prove that G is not planar.

Hint: If G satisfies the above properties, what is the minimum number of edges in G?

Problem A8: Let V be a set of cardinality n.  The number of digraphs (with self-loops allowed) with vertex set V can be derived as follows: We have n2  pairs of vertices, and for each pair u, v of vertices we have two choices: a digraph may or may not have an edge from u to v. So the number of these digraphs is 2n2 .

Modify this reasoning to derive the formula for the number of digraphs with vertex set V in which each vertex has outdegree equal d.  (We assume that n 2 d + 1.)

Problem A9: Let G = (V, E) be a planar graph with n vertices. Suppose that the set of edges E can be partitioned into two disjoint sets E1  and E2  such that both subgraphs (V, E1 ) and (V, E2 ) are trees. Determine the number of faces of G, as a function of n. Show your work.

Problem A10: Let d 2 2 be an integer.  A d-hypercube is a graph whose vertices are binary strings of length d and two vertices are adjacent if they differ on exactly one bit.  For example, a 2-hypercube is a square (a cycle of length 4) with vertices 00, 01, 11 and 10.  The picture below shows the 3-hypercube and the 4-hypercube (some edges are drawn with dashed lines for better clarity):

(a) For 3 points: Give a hamiltonian cycle for the 4-hypercube.  (Draw a picture.)

(b) For full credit:  Prove that for d 2 2 each d-hypercube has a hamiltonian cycle.  (Hint:  use induction on d.)

Problem A11: Give asymptotic solutions for the following recurrences:

Note: You must use correct notation.

Problem A12: Below you are given five choices of parameters p, q, e, d of RSA. For each choice tell whether these parameters are correct (write YES/NO). If yes, give a decryption of C = 2.  If not, give a brief justification (at most 10 words).

Let Bn  denote the number of different strings of length n that can be formed from these blocks. For example, for n = 5 we have B5 = 12 because we can form 12 strings of length 5:

(a) Set up a recurrence for Bn  and justify it.

(b) Solve this recurrence to find a formula for Bn .

Problem A14: Amber needs to buy 33 bagels for a party. There are three flavors to choose from: poppyseed, blueberry, and garlic. She needs at least 3 poppyseed bagels, at most 11 blueberry bagels and at most 13 garlic bagels. How many possible combinations of bagels are there that satisfy these