MATH2800 Introduction to Discrete Structures

Third Exam, Tuesday, April 24, 2007.

You may use one sheet of handwritten notes, but no other sources. The exam consists of six questions, and lasts fifty minutes. Please work all six problems. Please show all work clearly and in reasonable detail. Answers without appropriate supporting work or requested explanations may not receive full credit. No calculators are allowed.

1. (20 points) Let $f_n$ denote the $n$th Fibonacci number, so $f_0=0$, $f_1=1$, and $f_n=f_{n-1}+f_{n-2}$ for $n \geq 2$. Prove that
   
   $$f_1 + f_3 + \ldots + f_{2n-1} = f_{2n}$$
   
   
   when $n$ is a positive integer. (Hint: use induction.)

2. (20 points) One hundred students are taking a course in Discrete Structures. Thirty of the students are from upstate New York, and fifteen are from downstate New York. Fifty of the students have previously taken a course in Differential Equations. Of the students from upstate, 16 have previously taken a course in Differential Equations. Of the students from downstate, 11 have previously taken a course in Differential Equations. How many students in the Discrete Structures course are not from New York and have not previously taken a course in Differential Equations?

3. (20 points) Draw a graph with adjacency matrix
   
   $$\left[ \begin{array}{ccccccc} 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ ... ... 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \end{array} \right] .$$
   
   
   Is this graph isomorphic to the wheel $W_6$ with six outer vertices and a central hub? Justify your answer.

4. (10 points) Let $G=(V,E)$ be the following graph:
   
   
   

   What is the chromatic number of this graph? Demonstrate a coloring achieving the chromatic number. Why does there not exist a coloring using fewer colors?

5. (15 points) Let $G=(V,E)$ be the following graph:
   
   
   

   Find an Euler path in $G$. List the vertices in the order they appear on the path.

6. (15 points) Let $G=(V,E)$ be the following graph:
   
   
   

   Is this graph planar? Justify your answer.