CSC3001 Assignment 3 Solution

Instructions:
1. Print out this question paper (two-sided) and write down your full working on the blank area.
2. You can have discussions with your classmates. However, make sure all the solutions you submit are your own work. Any plagirism will be given ZERO mark.
4. Before your submission, please make a softcopy of your work for further discussion in a tutorial.
5. After making your softcopy, submit your assignment to the dropbox located on the 4th floor in Chengdao Building.
Student Number: Name:
1. Determine whether a graph exists for the following degree sequences:
1) 4,4,5,5,5,5 2) 1,2,3,4,4 3) 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.

hhhhhhDelivery manhhhhhhhh Deposite time Rabit Turtle Dinosaur Wolf
7:05 A
8:13 B
8:20 C
8:57 D
10:04 E
11:51 F
11:53 G
14:11 H
2. There are a few lockers in a building for the delivery men to deposite parcels. Each locker stores only one parcel at a time. There were 7 residents who picked up the parcels on a day. The system records the deposite time and pick-up time for each parcel as follows. (Note: the letters in the table entries indicate the different parcels.) hhhh
```````Residents````` Pick-up time Kiwi Moa Morepork Tuatara Kakapo Penguin Emu
9:31 C
10:50 A
11:58 E
12:01 F
12:42 G
15:23 H
16:15 B
17:35 D
```
Model this problem as a graph problem and determine the least number of lockers in the building.

3. In a standard stable matching problem, boys’ and girls’ preference are provided as follows. In order to obtain a stable matching, the boys are making proposals.
Boys’ preference boy preference order Girls’ preference girl preference order
b, a, d, e, c a
d, b, a, c, e b
b, e, c, d, a c
a, d, c, b, e d
AE, B, A, D, C BD, C, B, A, E
CB, C, D, E, A
DA, E, D, C, B
E b, d, a, e, c e D, B, E, C, A
But these girls have learned “Discrete Mathematics”. They complained that this is unfair, and two of them lied in their preference above. By the end of the marrying procedure, one obtains the following stable matching:
(A,a), (B,c), (C,b), (D,e), (E,d)
Can you figure out which girls lied?

4. Recall that an n-stair is the collection of the unit squares bounded by x-axis, y = x and x = n + 1. An n-stair graph is obtained by replacing each of the unit squares by a vertex where two vertices are adjacent if two unit squares share a common side. A Hamiltonian path of a graph is a simple path that visits all the vertices of the graph. Proof that no n-stair graph has a Hamiltionian path for any n ≥ 3.

5. Let G be a bipartite graph with bipartition (A,B) where |A| = |B| = 2n. Suppose that |N(X)| ≥ |X| for every X ⊆ A with |X| ≤ n, and |N(Y )| ≥ |Y | for every Y ⊆ B with |Y | ≤ n. Prove that G has a perfect matching.