METU Department of Mathematics Math 405 Combinatorics Spring 2010

Midterm 2

May 6 2010, 17:30 – 19:00, 4 problems: 15+15+15+15 pts

Name:

Problem 1. Find sequence a_{n} satisfying the following recurrence relations (a) a_{n} = a_{n−1} + 2a_{n−2} + 2n − 1, a_{0} = 2, a_{1} = 1;

(b) a_{n}^{2} = a_{n−1}^{2} + 2a_{n−2}^{2}, a_{0} = 2, a_{1} = 1;

(c) a_{n} = 4a\frac{n}{2} + 3, a_{1} = 1.

Problem 2. (a) Find labelled trees with the following two Prüfer’s codes: 321321 and 113111.

(b) A tree has vertices v_{1}, v_{2}, v_{3} of degrees 2,3 and 4 respectively, the other vertices are leaves. Find the number of leaves in such trees (give a general explanation, showing examples will NOT be accepted).

(c) Find the number of different (non-isomorphic) labelled trees with the vertices like in (b).

Problem 3. (a) Consider sets A_{1} = {1, 2, 4, 5}, A_{2} = {2, 3, 4, 7}, A_{3} = {2, 4, 5, 8}, A_{4} = {1, 4, 5, 8}. Sketch the corresponding bipartite graph and its matching matrix.

(b) Is it possible to choose two representatives from each set, so that totally all 8 elements will be chosen ? (Check the condition in the Harem theorem to explain your answer !)

(c) Sketch a bipartite graph represented by the following matching matrix ( \begin{matrix}0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 \end{matrix} )

Problem 4. (a) For the following oriented graph Γ find the incidence matrix A

(b) Is there an oriented Hamiltonian path in this graph ? (Either find it, or explain why it does not exist).

(c) Find a minimal edge-covering of Γ;

(d) Give examples of three different spanning trees in graph Γ

(e) Find matrix AA^{T} and use it to find the number of spanning trees in graph Γ.