Instructions:
1. This exam is 120 minute long.
2. The total mark in this exam paper is 110, and the maximum you can get is 100. You should try to attempt as many questions as possible.
3. This exam has 14 pages, consisting of 7 questions. Write down your full working in this exam paper.
5. Calculators are allowed.
6. This exam is in closed book format. No books, dictionaries or blank papers to be brought in except one page of A4 size paper note which you can write anything on both sides. Any cheating will be given ZERO mark.
Student Number: Name:
1. (19 points)
(b) Let A,B,C ⊆ R. Which of the following identities are true? If the identity is true, prove it; otherwise, give a counterexample.
(i) (A ∩ B) × C = (A ∩ C) × (B ∩ C) (ii) (A − B) × C = (A × C) − (B × C)
2
2. (10 points) Let S ⊆ {1,2,...,100} be of size 25. Prove that there exist mutually distinct a,b,c,d ∈ S such that a + b = c + d.
4
3. (11 points) Suppose our library keeps several copies of the book “The Grant’s Solutions” in the stock. The following are its borrow/return records in this semester.
2/9 Li Lei, Ken
8/9 Han Meimei
10/9 Anne
20/9 Li Lei
28/9 Ken
8/10 Sue
9/10 Han Meimei
17/10 Li Lei
27/10 Han Meimei
2/11 Anne
11/11 Peter
19/11 Li Lei
27/11 Sue
3/12 Li Lei
10/12 Peter
13/12 Li Lei, Han Meimei
PP
Model this problem as a graph problem and determine the minimum number of copies that are kept in our library.
4. 25 points Determine whether a graph exists for the following degree sequences:
1) 1,2,2,3 2) 4,4,5,5,5,5 3) 2,2,3,3,3 4) 1,2,3,4,4 5) 1,1,1,2,2,3
If it exists, draw all the possibilities up to isomorphism and determine whether these graphs are planar; otherwise, explain why it does not exist.
5. 10 points Suppose the preferences between 4 boys and 4 girls are as follows.
Boys’ preference boy preference order Girls’ preference girl preference order
C,B,A,D A
A,C,B,D B
C,D,A,B C
14,3,1,2
22,3,4,1
34,3,1,2
4 D,C,B,A D 3,4,2,1
Determine whether the following matching is stable or not.
{(1,A),(2,D),(3,B),(4,C)}
If yes, prove it; otherwise list all the unstable pairs.
6. 15 points Let n ≥ 2 be an integer and let G = (V,E) be a bipartite graph with V = {a1,a2,...,an,b1,b2,...,bn} and E = {aibj|i 6= j}.
7. 20 points Let G be a k-regular graph with n vertices such that
• every pair of adjacent vertices has λ common neighbors; and • every pair of non-adjacent vertices has µ common neighbors.
for some k,n ∈ Z+ and λ,µ ∈ N.
